Computer science you might (not) want to know

Andy Andrea�Rails Conf 2022

Who I am and who I am not

Things to know

• CS: Computer Science
• Space: Memory (typically RAM)

​

• Whenever we’re discussing logs/logarithms, assume base 2

​

• For further information:
• 🔎 refers to a term you can search for more information

Part 1: Numbers

What exactly is a number anyway?

Base 10

​

7053

​

7*10³ + 0*10² + 5*10¹ + 3*10⁰

​

7*1000 + 0*100 + 5*10 + 3*1

​

What exactly is a number anyway?�Bases

Binary

1111₂

1*2³ + 1*2² + 1*2¹ + 1*2⁰

8 + 4 + 2 + 1

15₁₀

• Just another base where the max value for a digit is 1 instead of 9
• A single digit is a bit
• Eight bits is a byte

1111₁₀

1*10³ + 1*10² + 1*10¹ + 1*10⁰

1000 + 100 + 10 + 1

1111₁₀

Fractions: decimal versus bicimal

• As in base 10, we define a certain position to be the radix point

​

481.235 in decimal

​

​

​

​

​

​

110.011 in bicimal (6.375 in decimal)

Fractions

• Many numbers can only be represented by a formula or an infinitely long decimal
• e.g. ⅓₁₀ → 0.3333333…₁₀
• Numbers can be represented with a finite number of digits in one base but not another
• ⅓₁₀ → 0.1₃ → 0.4₁₂
• 0.2₁₀ → 0.00110011...₂
• Infinite digits requires infinite storage

🔎 Why base 12 is better�🔎 How floating point numbers are stored (exponent, significand, etc)

The float problem

Solution 1: truncate to a certain number of digits and round

• Ruby’s Float
• Pros
• Space
• Cons
• Imprecise

The float problem

Solution 2: Store fractions as an equation, e.g. ⅓

• Ruby’s Rational
• Pros:
• Precise
• Cons
• Having to track numerators and denominators can be expensive, hard to read

The float problem

Solution 3: Store fractions as an array of digits with an exponent

• Ruby’s BigDecimal
• Pros:
• Precise
• Cons
• Space

​

​

​

​

​

🔎 The Real struct in bigdecimal.h in the BigDecimal source

🔎 BigDecimal(Variable Precision Floating Library for Ruby)

Other issues with numbers

• Large numbers
• Arbitrarily large numbers require an arbitrarily high amount of space
• Negative numbers
• Overflows and underflows

0111 + 1

-8..7

0111

​

🔎 Two’s Complement

🔎 JavaScript’s Number.MAX_VALUE vs Number.MAX_SAFE_INTEGER

🔎 Ruby’s Integer (>= Ruby 2.4) and Bignum (< 2.4)

🔎 Gandhi Civilization Overflow

Why do you want to know: Binary

• When to use floats versus decimals
• When you’re at risk for an overflow or unsupported behavior

​

​

​

​

​

🔎Bitwise operators and methods e.g.

• AND (&)
• OR (|)
• XOR (^)
• NOT (~)
• Left shift (<<)
• Right shift (>>)

Why do you not need to know: Binary

• Not often very relevant to Rails apps
• We can understand how and when to use something even if we don’t exactly how it works

Part 2: Algorithms

“Algorithm” defined

“A process or set of rules to be followed in calculations or other problem-solving operations, especially by a computer”

https://www.lexico.com/en/definition/algorithm

Sorting algorithms

Visualization and Comparison of Sorting Algorithms by Viktor Bohush on YouTube

Comparing algorithms

Sorting Algorithm on Wikipedia

Algorithmic analysis

• When f(n) is an algorithm that takes input of length n
• O(f(n)) (“Big O”) is basically the worst case
• Ω(f(n)) (“Big Omega”) is basically the best case
• Θ(f(n)) (“Big Theta”) is basically the average case

• Quick sort
• O(n²)
• Ω(n*log(n))
• Θ(n*log(n))

Time/space complexity

• From best to worst:
• 1
• log(n)
• √n
• n
• n*log(n)
• n²
• n³
• 2ⁿ
• n!

WolframAlpha.com

Constant time (O(1))

One line of code gets executed one time regardless of input

Linear time (O(n))

The two lines within our block get executed n (or numbers.length) times giving us 2n

The puts gets executed once giving us 1

0

Linear time (O(n))

• Total number of executions: 2n + 1 => O(n)
• Constants/lesser terms become negligible as n approaches Infinity
• Effect of coefficients depend on operation and platform

Algorithms in real life

Algorithms in real life: O(n) example

Algorithms in real life: Improving on O(n)

Algorithms in real life: Improving on O(n)

Algorithms in real life: Improving on O(n)

The binary search algorithm

🔎Depth-first search

🔎Breadth-first search

Binary search in the wild: git bisect

man git-bisect

​

🔎RSpec bisect

Why do you want to know: Algorithms

• Write and use more efficient solutions/data structures
• Good to know how things will scale as data increases in size
• Shared language

Why do you not want to know: Algorithms

• Algorithmic complexity is often not the bottleneck for web apps
• Database calls, network requests should take much longer
• Algorithmic complexity is a poor metric in real applications
• Algorithms can be misused
• Ruby/Rails/databases/etc hide a lot of implementation and optimization

Conclusion: why do you want to know computer science?

• Interviews
• Shared language
• Increased understanding of some tools
• Handy when doing lower level or more CS-heavy work

Conclusion: why do you not want to know computer science?

• Getting caught up in theory can impact reality
• Disconnect between practical software development/academic CS/hiring

Conclusion: why do you not want to know computer science?

• Getting caught up in theory can impact reality
• Disconnect between practical software development/academic CS/hiring

​

• You don’t need to know it because you can learn it