Introduction

This document codifies the standard algorithms used by grade school students for rational numbers, equality, inequality, and arithmetic. It originally started as a pre-algebra refresher and instead morphed into what it is now.

Place Value System

The place value system is the modern way in which numbers are represented. A number represented using the place value system is made up of a string of symbols separated by a dot, where each (index, symbol) combination in the string represents a value (i.e. val[idx] = compute(idx, str[idx])).

The symbols used to represent a number are called digits. All digits to the...

These wholes and fractional are combined to represent the final value for the number. For example, the number 43.5 represents...

●●●●●●●●●●
●●●●●●●●●●
●●●●●●●●●●
●●●●●●●●●●  ●●●     ◑
    4        3   .  5

The grammar for the place value system is...

number: whole (DOT fractional)?;
whole: DIGIT+;
fractional: DIGIT+;

DOT: '.';
DIGIT: [0123456789];

The entry point to the grammar is the number rule. Note that the fractional part of the number rule is optional -- a number with a missing fractional part is assumed to have no partial value -- it consists of only entire objects.

⚠️NOTE️️️⚠️

The details below describe each sub-rule as well as the algorithm to process that sub-rule. None of the algorithms use actual numbers / number operations -- value is tracked by iteratively pushing blocks into arrays. Why create an algorithm without using numbers? Using numbers to describe numbers is circular logic.

The whole rule is used to express how many entire objects there are. The algorithm for determining that value consists of 3 steps:

  1. Determine the value each digit represents...

    0 = <empty>
    1 = ●
    2 = ●●
    3 = ●●●
    4 = ●●●●
    5 = ●●●●●
    6 = ●●●●●●
    7 = ●●●●●●●
    8 = ●●●●●●●●
    9 = ●●●●●●●●●
    

    These are the digits and their values.

  2. Then, calculate the value for each index of the whole part. The algorithm for determining the value of each index is...

    index_values = []
    for (item in index) {
      next_index_value = <empty>
      if (index_values.isEmpty()) {
        index_values.push(●)
      } else {
        last_index_value = index_value[-1]
        for (inner_item in ●●●●●●●●●●) {   // the number of dots here should be 1 more than the value of the largest symbol
          next_index_value.push(last_index_value)
        }
      }
    }
    index_values.reverse()
    

    For example, the index values in the whole part 572 are...

    _ _ _
    │ │ │
    │ │ └─ ● 
    │ └─── ●●●●●●●●●●
    └───── ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
    
  3. Now that the digit values and index values are known, the value of each (digit, index) combination can be calculated. The algorithm for determining the value of each (digit, index) combination is...

    final_value = <empty>
    for (digit_value, index_value) in input
      value = <empty>
      for item in digit_value
        value.push(index_value)
    

    For example, the (digit, index) values in the whole part 572 are....

    Those values combined together would be...

    5 7 2
    │ │ │
    │ │ └─ ●
    │ │    ● 
    │ │
    │ └─── ●●●●●●●●●●
    │      ●●●●●●●●●●
    │      ●●●●●●●●●●
    │      ●●●●●●●●●●
    │      ●●●●●●●●●●
    │      ●●●●●●●●●●
    │      ●●●●●●●●●●
    │
    └───── ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
           ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
           ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
           ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
           ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
    

The fractional rule is used to express some portion of an object (less than a single object). Conceptually, you can think of each digit in the fractional string as a recursive slicing of a single whole. For example, in the fractional string 358, the first index picks out 3 equal parts out of the whole ...

Concept diagram for partial rule 3

, ... the second index picks out 5 equal parts out of the NEXT part of the whole ...

Concept diagram for partial rule 35

, ... the third index picks out 8 equal parts out of the NEXT part of the previous part ...

Concept diagram for partial rule 358

.

⚠️NOTE️️️⚠️

Trouble seeing this final partition? Open the above image up standalone and zoom in. It's an SVG.

This is exactly the same as chopping up a whole into 1000 equal parts and picking 358 of those parts...

Concept diagram for partial rule 358

The algorithm for processing the fractional rule is similar to the conceptual model described above. It consists of 2 steps:

  1. Determine the total number of parts there are. The algorithm for this is...

    total_parts = <empty>
    for (item in index) {
      if (total_parts == <empty>) {
        total_parts.push(●●●●●●●●●●) // the number of dots here should be 1 more than the value of the largest digit
      } else {
        new_total_parts = <empty>
        for (inner_item in ●●●●●●●●●●) {  // the number of dots here should be 1 more than the value of the largest digit
          new_total_parts.push(total_parts)
        }
        total_parts = new_total_parts
      }
    }
    

    For example, for a fractional part of 55 the total number of parts would be 100...

    ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
    

    ⚠️NOTE️️️⚠️

    An easier way to do the same thing is...

    1. add an extra index.
    2. set the first index to 1.
    3. set all other indexes to 0.

    So if the fractional string has 2 digits (as 55 does), the total number of parts would be 100.

    The reason why the code above doesn't do this is because I'm trying to avoid the use of numbers and operations that haven't been introduced yet.

    ⚠️NOTE️️️⚠️

    Know exponents? Doing 10^fractional.length is the same thing.

    If the fractional string has 2 digits (as 55 does), the total number of parts would be 10^2=100.

    The reason why the code above doesn't do this is because I'm trying to avoid the use of numbers and operations that haven't been introduced yet.

  2. The fractional string is a selection out the total parts calculated in the step above.

    For example, for a fractional part of 55, ...

    [●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●]●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
    

    Concept diagram for partial rule 55

Similar to the sliced circle diagrams shown in the algorithm descriptions above, a number line may also be used to visualize the value that a number represents. It consists of a straight horizontal line with equidistant vertical notches spliced through out, where each notch is labelled with incrementally larger numbers from left-to-right...

Kroki diagram output

The number being represented is marked on the line. For example, to represent the number 5...

Kroki diagram output

Numbers with fractional parts may also be marked on the line. Move the marker to the whole part of the number, then determine the amount of space that the fractional part consumes and move over that much towards the next notch. For example, to represent the number 5.5...

Concept diagram for fraction 0 / 2

First, move the marker over to the whole: 5...

Kroki diagram output

Then, determine how much space in the fractional part was consumed. 5.5's fractional part takes up half a circle, so it gets moved half way towards the next notch...

Kroki diagram output

Equality

↩PREREQUISITES↩

Equality is the concept of checking if one number to see if it has the same value as another number. In other words, checking if both numbers are the same. For example, the numbers 5 and 5 are the same number, so they're said to be equal.

If you were to visualize both numbers on a number line, they would both sit at the same position...

Kroki diagram output

Equality is typically represented using the infix operator = or ==. The above example would be represented as 5=5.

The output of an equality operation is either true or false: true when the numbers are the same and false when they aren't. For example, ...

When using words, equality is typically represented using the following syntax:

⚠️NOTE️️️⚠️

Not all of the above are bookmarked because there's too much ambiguity. For example, the word "is" is used in many contexts outside of addition.

⚠️NOTE️️️⚠️

If you know algebra, the word "gives" is applicable more so to algebra and beyond. For example: the addition of x and 1 gives 5 means x+1 = 5.

The opposite of equality is not equality. That is, not equality is the concept of checking if one number has a different number of items than another number. For example, the numbers 5 and 6 are different, so they're said to be not equal.

Not equality is typically represented using the infix operator ≠ or !=. The above example would be represented as 5≠6.

The output of a not equality operation is either true or false: true when the numbers are different and false when they're the same. For example, ...

When using words, not equality is typically represented using the following syntax:

⚠️NOTE️️️⚠️

Not all of the above are bookmarked because there's too much ambiguity. For example, the words "is not" is used in many contexts outside of addition.

⚠️NOTE️️️⚠️

Sometimes you may see the word inequality. This refers to operations that compare two numbers for something other than equality: greater than (>), less than (<), not equality (≠), and potentially others.

Greater Than

↩PREREQUISITES↩

Greater than is the concept of checking if one number represents more items than another number. For example, the number 8 has more items than the number 5, so 8 is said to be greater than 5.

If you were to visualize both numbers on a number line, the number 8 would be ahead of 5...

Kroki diagram output

Greater than is typically represented using the infix operator >. The above example would be represented as 8>5.

The output of a greater than operation is either true or false: true when the first number has more items and false when it doesn't. For example, ...

When using words, greater than is typically represented using the following syntax:

Greater than or equal is common shorthand to compare if a number is greater than or equal to some other number. It's typically represented using the infix operator ≥ or >=. For example...

When using words, greater than or equal is typically represented using the following syntax:

⚠️NOTE️️️⚠️

Think of at least as "not less than" -- 8 is not less than 5. If you can follow the logic...

Less Than

↩PREREQUISITES↩

Less than is the concept of checking if one number has fewer items than another number. For example, the number 5 has fewer items than the number 8, so 5 is said to be less than 8.

If you were to visualize both numbers on a number line, the number 5 would be behind of 8...

Kroki diagram output

Less than is typically represented using the infix operator <. The above example would be represented as 5<8.

The output of a less than operation is either true or false: true when the first number has fewer items and false when it doesn't. For example, ...

When using words, less than is typically represented using the following syntax:

Less than or equal is common shorthand to compare if a number is less than or equal to some other number. It's typically represented using the infix operator ≤ or <=. For example...

When using words, less than or equal is typically represented using the following syntax:

⚠️NOTE️️️⚠️

Think of at most as "not more than" -- 5 is not more than 8. If you can follow the logic...

Addition

↩PREREQUISITES↩

Addition is the concept of taking two numbers and combining their values together. For example, combining 3 items and 5 items together results in 7 items...

 [●●●]    [●●●●●]
   3         5

group values together

   [●●●●●●●●]
       7

Addition is typically represented using the infix operator +. The above example would be represented as 3+5.

The output of an addition operation is called the sum. In the example above, 7 is the sum.

When using words, addition is typically represented using the following syntax:

⚠️NOTE️️️⚠️

More than, larger than, and greater than are more much more commonly used for the greater than relational operator. For example...

You'll need to disambiguate based on the context.

Properties of addition:

Subtraction

↩PREREQUISITES↩

Subtraction is the concept of removing the value of one number from another number. For example, removing 3 items from 5 items results in 2 items...

    [●●●●●]
       5

pick out 3 from the 5

   [●●] [●●●]
    2     3

Subtraction is typically represented using the infix operator -. The above example would be represented as 5-3.

The output of an subtraction operation is called the difference. In the example above, 2 is the difference.

When using words, subtraction is typically represented using the following syntax:

⚠️NOTE️️️⚠️

Fewer than, smaller than, and less than are more much more commonly used for the less than relational operator. For example...

You'll need to disambiguate based on the context.

Properties of subtraction:

⚠️NOTE️️️⚠️

Unlike addition, subtraction is not commutative. 5-3 isn't the same as 3-5

Multiplication

↩PREREQUISITES↩

Multiplication is the concept of taking a number and iteratively adding it to itself a certain number of iterations. For example, 3 added to itself for 5 iterations results in 15 items...

3+3+3+3+3=15

 [●●●] 3
 [●●●] 3
 [●●●] 3
 [●●●] 3
 [●●●] 3

Multiplication is typically represented using the infix operator *. The above example would be represented as 3*5. When written in formal math notation, it may also be written as...

⚠️NOTE️️️⚠️

Know algebra? Do not use x or a cross as a symbol for multiplication. It causes confusion for algebra expressions because x can also be a variable.

The output of a multiplication operation is called the product. In the example above, 15 is the product.

The inputs into the multiplication operation are either...

When using words, multiplication is typically represented using the following syntax:

⚠️NOTE️️️⚠️

There are certain special words that denote multiplication. For example, the word twice means 2 multiplied by something else -- e.g. twice 5 is the same thing as 2*5.

Much less common is the word thrice -- it means 3 times something else. The pattern here seems to be the add "ice" to the end of the number? Unsure, but Google seems to give a definition for fourice.

Properties of multiplication:

Division

↩PREREQUISITES↩

Division is the concept of taking a number and iteratively subtracting it by another number to find out how many iterations it can be subtracted. For example, 15 can be subtracted by 3 exactly 5 iterations before nothing's left...

 [●●●●●●●●●●●●●●●] start with 15

 [●●●●●●●●●●●●] 15-3=12 (iteration 1)
 [●●●●●●●●●] 12-3=9 (iteration 2)
 [●●●●●●] 9-3=6 (iteration 3)
 [●●●] 6-3=3 (iteration 4)
 [] 3-3=0 (iteration 5)

Another way of thinking about division is that it's chopping up a number. Imagine cutting up a pie into 15 pieces and eating 3 pieces at a time. The pie will be done after you've eaten 5 times.

Concept diagram for fraction 0 / 15

Concept diagram for fraction 0 / 15

Concept diagram for fraction 0 / 15

Concept diagram for fraction 0 / 15

Concept diagram for fraction 0 / 15

In certain cases, division may result in some remaining value that isn't large enough for another subtraction iteration to take place. This remaining value is called the remainder For example, 16 can be subtracted by 3 for 5 iterations but will have a remainder of 1...

 [●●●●●●●●●●●●●●●●] start with 16

 [●●●●●●●●●●●●●] 16-3=13 (iteration 1)
 [●●●●●●●●●●] 13-3=10 (iteration 2)
 [●●●●●●●] 10-3=7 (iteration 3)
 [●●●●] 7-3=4 (iteration 4)
 [●] 4-3=1 (iteration 5)

 only 1 item left -- not enough for another subtraction iteration
 
 1 is the remainder

⚠️NOTE️️️⚠️

If a division operation results in no remainder, it's said to be divisible.

Division is typically represented using the infix operator / or ÷. The above example would be represented as 15/3 or 15÷3. It may also be written as 153\frac{15}{3}, which is just a fancier way of writing 15/3.

The output of a division operation is called the quotient. In the example above, the quotient is 5 (it subtracts 5 times).

The inputs into the division operation are called the dividend and divisor. In the example above, 15 is the dividend and 3 is the divisor.

⚠️NOTE️️️⚠️

One way to think of this is that the dividend (the number on the left / top) is the starting value, and the divisor is the number being iteratively subtracted.

The quotient is the number of times you can subtract.

When using words, division is typically represented using the following syntax:

⚠️NOTE️️️⚠️

There are certain special words that denote division. For example, the word ...

Properties of division:

Whole Number

↩PREREQUISITES↩

Kroki diagram output

Whole numbers are numbers which have no fractional part -- they only consist of wholes. For example, 5, 0, 104, and 27 are whole numbers while 4.2 is not.

Kroki diagram output

The difference between whole numbers and natural / counting / cardinal numbers is that counting numbers don't include 0 (they start at 1). That is, counting numbers start where you start counting / where something exists. For example, if you're counting apples, you start counting at 1 -- there needs to be at least 1 apple to start.

Equality

↩PREREQUISITES↩

The algorithm used by humans to test for whole number equality relies on two idea...

  1. If two whole numbers are equal then they must have the same number of digits. For example, 55 and 9123456 aren't equal because the number of digits between them isn't the same -- 55 has 2 digits while 9123456 has 7 digits.

    ⚠️NOTE️️️⚠️

    This assumes that any prepended 0 digits have been removed. Recall that 07, 007, 0007, ... all represent the same value: 7.

  2. Numbers represented in place-value notation can be broken down into single digit components -- the place of each digit in the number represents some portion of that number's value. For example, the number 935 can be broken down as 9 100s, 3 10s, and 5 1s...

    100
    100
    100
    100
    100            1
    100            1
    100     10     1
    100     10     1
    100     10     1
    ---     --     -
    900     30     5
    
    
    
    9 3 5
    │ │ │
    │ │ └─ ●
    │ │    ● 
    │ │    ● 
    │ │    ● 
    │ │    ● 
    │ │
    │ └─── ●●●●●●●●●●
    │      ●●●●●●●●●●
    │      ●●●●●●●●●●
    │
    └───── ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
           ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
           ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
           ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
           ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
           ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
           ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
           ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
           ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
    

Since the numbers being tested for equality must have the same number of digits between them, the first test to see if they may be equal is to a ensure that the number of digits are equal (idea 1). For example, 55 has 2 digits while 9123456 has 7 digits -- there's no point in going any further because if the number of digits aren't the same then there's no way for the actual numbers to be the same.

If it turns out that the number of digits are the same, then each place's digit is tested for equality (idea 2). If all the digits are equal, then the numbers are equal. For example, the numbers 195 and 195 are equal...

1 9 5
| | |
1 9 5

... while the numbers 175 and 195 are not equal...

1 7 5
| x |
1 9 5

The way to perform this algorithm via code is as follows...

arithmetic_code/WholeNumber.py (lines 139 to 158):

@log_decorator
def __eq__(lhs: WholeNumber, rhs: WholeNumber) -> bool:
    if isinstance(rhs, int):
        rhs = WholeNumber.from_int(rhs)
    elif isinstance(rhs, str):
        rhs = WholeNumber.from_str(rhs)

    if not isinstance(rhs, WholeNumber):
        raise Exception()

    log(f'Equality testing {lhs} and {rhs}...')
    log_indent()

    ret = lhs.digits == rhs.digits

    log_unindent()
    log(f'{ret}')

    return ret

⚠️NOTE️️️⚠️

The code is making use of python lists to do the 2 tests above. Python's list equality already applies ideas 1 and 2 internally to determine if the contents of the list are equal.

Less Than

↩PREREQUISITES↩

The algorithm used by humans to test for whole number less than relies on the idea that numbers represented in place-value notation can be broken down into single digit components -- the place of each digit in the number represents some portion of that number's value. For example, the number 935 can be broken down as 9 100s, 3 10s, and 5 1s...

100
100
100
100
100            1
100            1
100     10     1
100     10     1
100     10     1
---     --     -
900     30     5



9 3 5
│ │ │
│ │ └─ ●
│ │    ● 
│ │    ● 
│ │    ● 
│ │    ● 
│ │
│ └─── ●●●●●●●●●●
│      ●●●●●●●●●●
│      ●●●●●●●●●●
│
└───── ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
       ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
       ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
       ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
       ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
       ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
       ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
       ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
       ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●

Since a number can be broken down into single digit components, each single digit component from the numbers being compared can individually tested from most significant to least significant (left-to-right). If a digit from the number being tested is...

If no more digits are remaining for testing, the number being tested is equal.

For example, imagine testing the number 23 and 21...

2 3                      2 1
│ │                      │ │
│ └─ ●                   │ └─ ●
│    ●                   │
│    ●                   └─── ●●●●●●●●●●
│                             ●●●●●●●●●●
└─── ●●●●●●●●●●
     ●●●●●●●●●●

The first digits are equal (2 == 2), so move to the next digit. The next digit is larger than the other digit (3 > 1), so 23 is not less than 21.

⚠️NOTE️️️⚠️

What happens when the number of digits aren't the same between the numbers being tested (e.g. 55 and 12345)? Recall how place-value notation works. 0 can be used when a corresponding digit doesn't exist at some position.

The way to perform this algorithm via code is as follows...

arithmetic_code/WholeNumber.py (lines 161 to 188):

@log_decorator
def __lt__(lhs: WholeNumber, rhs: WholeNumber) -> bool:
    if isinstance(rhs, int):
        rhs = WholeNumber.from_int(rhs)
    elif isinstance(rhs, str):
        rhs = WholeNumber.from_str(rhs)

    if not isinstance(rhs, WholeNumber):
        raise Exception()

    log(f'Less than testing {lhs} and {rhs}...')
    log_indent()

    count = max(len(lhs.digits), len(rhs.digits))
    for pos in reversed(range(0, count)):  # from smallest to largest component
        log(f'Test digits {lhs[pos]} and {rhs[pos]}...')
        if lhs[pos] > rhs[pos]:
            log(f'{lhs[pos]} > {rhs[pos]} -- {lhs} is NOT less than {rhs}, it is greater than')
            return False
        elif lhs[pos] < rhs[pos]:
            log(f'{lhs[pos]} < {rhs[pos]} -- {lhs} is less than {rhs}')
            return True
        else:
            log(f'{lhs[pos]} == {rhs[pos]} -- continuing testing')

    log(f'No more digits to test -- {lhs} is NOT less than {rhs}, it is equal')
    return False

Greater Than

↩PREREQUISITES↩

The algorithm used by humans to test for whole number greater than relies on the idea that numbers represented in place-value notation can be broken down into single digit components -- the place of each digit in the number represents some portion of that number's value. For example, the number 935 can be broken down as 9 100s, 3 10s, and 5 1s...

100
100
100
100
100            1
100            1
100     10     1
100     10     1
100     10     1
---     --     -
900     30     5



9 3 5
│ │ │
│ │ └─ ●
│ │    ● 
│ │    ● 
│ │    ● 
│ │    ● 
│ │
│ └─── ●●●●●●●●●●
│      ●●●●●●●●●●
│      ●●●●●●●●●●
│
└───── ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
       ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
       ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
       ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
       ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
       ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
       ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
       ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
       ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●

Since a number can be broken down into single digit components, each single digit component from the numbers being compared can individually tested from most significant to least significant (left-to-right). If a digit from the number being tested is...

If no more digits are remaining for testing, the number being tested is equal.

For example, imagine testing the number 23 and 21...

2 3                      2 1
│ │                      │ │
│ └─ ●                   │ └─ ●
│    ●                   │
│    ●                   └─── ●●●●●●●●●●
│                             ●●●●●●●●●●
└─── ●●●●●●●●●●
     ●●●●●●●●●●

The first digits are equal (2 == 2), so move to the next digit. The next digit is larger than the other digit (3 > 1), so 23 is greater than than 21.

⚠️NOTE️️️⚠️

What happens when the number of digits aren't the same between the numbers being tested (e.g. 55 and 12345)? Recall how place-value notation works. 0 can be used when a corresponding digit doesn't exist at some position.

The way to perform this algorithm via code is as follows...

arithmetic_code/WholeNumber.py (lines 194 to 221):

@log_decorator
def __gt__(lhs: WholeNumber, rhs: WholeNumber) -> bool:
    if isinstance(rhs, int):
        rhs = WholeNumber.from_int(rhs)
    elif isinstance(rhs, str):
        rhs = WholeNumber.from_str(rhs)

    if not isinstance(rhs, WholeNumber):
        raise Exception()

    log(f'Greater than testing {lhs} and {rhs}...')
    log_indent()

    count = max(len(lhs.digits), len(rhs.digits))
    for pos in reversed(range(0, count)):  # from smallest to largest component
        log(f'Test digits {lhs[pos]} and {rhs[pos]}...')
        if lhs[pos] > rhs[pos]:
            log(f'{lhs[pos]} > {rhs[pos]} -- {lhs} is greater than {rhs}')
            return True
        elif lhs[pos] < rhs[pos]:
            log(f'{lhs[pos]} < {rhs[pos]} -- {lhs} is NOT greater than {rhs}, it is less than')
            return False
        else:
            log(f'{lhs[pos]} == {rhs[pos]} -- continuing testing')

    log(f'No more digits to test -- {lhs} is NOT greater than {rhs}, it is equal')
    return False

Addition

↩PREREQUISITES↩

The algorithm used by humans to add large whole numbers together is called vertical addition. Vertical addition relies on two ideas...

  1. Humans can easily add a single digit number to another single digit number without much effort. For example...

    ... are all addition operations that don't take much effort / are already probably cached in person's memory.

  2. Numbers represented in place-value notation can be broken down into single digit components -- the place of each digit in the number represents some portion of that number's value. For example, the number 935 can be broken down as 9 100s, 3 10s, and 5 1s...

    100
    100
    100
    100
    100            1
    100            1
    100     10     1
    100     10     1
    100     10     1
    ---     --     -
    900     30     5
    
    
    
    9 3 5
    │ │ │
    │ │ └─ ●
    │ │    ● 
    │ │    ● 
    │ │    ● 
    │ │    ● 
    │ │
    │ └─── ●●●●●●●●●●
    │      ●●●●●●●●●●
    │      ●●●●●●●●●●
    │
    └───── ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
           ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
           ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
           ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
           ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
           ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
           ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
           ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
           ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
    

Since a number can be broken down into single digit components and adding a single digit to any number is easy, any two numbers can be added by adding their individual single digit components. For example, the number 53 and 21 are broken down as follows...

5 3                      2 1
│ │                      │ │
│ └─ ●                   │ └─ ●
│    ●                   │
│    ●                   └─── ●●●●●●●●●●
│                             ●●●●●●●●●●
└─── ●●●●●●●●●●
     ●●●●●●●●●●
     ●●●●●●●●●●
     ●●●●●●●●●●
     ●●●●●●●●●●

Add their individual single digit components together to get the sum. The ...

7 4
│ │
│ └─ ●
│    ● 
│    ● 
│    ● 
│
└─── ●●●●●●●●●●
     ●●●●●●●●●●
     ●●●●●●●●●●
     ●●●●●●●●●●
     ●●●●●●●●●●
     ●●●●●●●●●●
     ●●●●●●●●●●

In certain cases, the addition of two single digit components may bleed over to the next single digit component. For example, adding 93 and 21 can be broken down as follows...

Combining the 10s place resulted in a bleed over to the hundreds place. This extra 100s place bleed over digit can be carried over and combined into the hundreds place. This process is called carry-over -- you're carrying-over the extra bleed over digit to its correct place and combining it with whatever else is there.

Conceptually, carrying-over is the idea of breaking out a group of 10 from the current place and moving them over to the next highest place (e.g. 10s place to 100s place). For example, when adding 93 to 21, adding the digits at the 10's place (90+20) results in 110...

9 3                      2 1
│ │                      │ │
│ └─ ●                   │ └─ ●
│    ●                   │
│    ●                   └─── ●●●●●●●●●●
│                             ●●●●●●●●●●
└─── ●●●●●●●●●●
     ●●●●●●●●●●
     ●●●●●●●●●●
     ●●●●●●●●●●
     ●●●●●●●●●●
     ●●●●●●●●●●
     ●●●●●●●●●●
     ●●●●●●●●●●
     ●●●●●●●●●●

results in 

11 4
│  │
│  └─ ●
│     ● 
│     ● 
│     ● 
│
└─── ●●●●●●●●●●
     ●●●●●●●●●●
     ●●●●●●●●●●
     ●●●●●●●●●●
     ●●●●●●●●●●
     ●●●●●●●●●●
     ●●●●●●●●●●
     ●●●●●●●●●●
     ●●●●●●●●●●
     ●●●●●●●●●●
     ●●●●●●●●●●

Since 11 is too many digits for the tens place (each place must only have 1 digit), break out 10 groups from the 10s place and move those over to the 100s place...

11 4
│  │
│  └─ ●
│     ● 
│     ● 
│     ● 
│
└─── ●●●●●●●●●●
    ┌──────────┐
    │●●●●●●●●●●│
    │●●●●●●●●●●│ each group is 10 items and we grabbed 10 of them (that's 100 items total)
    │●●●●●●●●●●│
    │●●●●●●●●●●│
    │●●●●●●●●●●│
    │●●●●●●●●●●│
    │●●●●●●●●●●│
    │●●●●●●●●●●│
    │●●●●●●●●●●│
    │●●●●●●●●●●│
    └──────────┘

move those 100 items as 1 group of 100s

1 1 4
│ │ │
│ │ └─ ●
│ │    ● 
│ │    ● 
│ │    ● 
│ │
│ └─── ●●●●●●●●●●
│     ┌────────────────────────────────────────────────────────────────────────────────────────────────────┐
└─────│●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●│
      └────────────────────────────────────────────────────────────────────────────────────────────────────┘

The digit in the 10s place is the result for the 10s place, while the digit in the 100s place gets combined in with the 100s place. In the above example, the 100s place was empty, so the carry-over remained as-is.

The way to perform this algorithm in real-life is to stack the two numbers being added on top of each other, where the positions for both numbers match up (e.g. the 1s position matches up, the 10s position matches up, the 100s position matched up, etc..). Then, add the individual single digit components together (from right-to-left). For example...

15321+174\begin{alignedat}{3}{1}& \enspace{5}& \enspace{3}& \{ }& \enspace{2}& \enspace{1}& \enspace + \ \hline{1}& \enspace{7}& \enspace{4}&\end{alignedat}

⚠️NOTE️️️⚠️

The number 21 has nothing in its 100s place -- nothing is the same as 0. 21 is the same as 021.

If 2 individual single digit components combine together to results in an extra digit (e.g. 5+8=13), the bleed over digit is carried over to the next position (on the left). This is denoted by stacking the bleed over digit on top of the next position -- it's being combined along with the other digits at that position. For example...

155181+632\begin{alignedat}{3}{1}& \enspace{ }& \enspace{ }& \{5}& \enspace{5}& \enspace{1}& \{ }& \enspace{8}& \enspace{1}& \enspace + \ \hline{6}& \enspace{3}& \enspace{2}&\end{alignedat}

The way to perform this algorithm via code is as follows...

arithmetic_code/WholeNumber.py (lines 227 to 284):

@log_decorator
def __add__(lhs: WholeNumber, rhs: WholeNumber) -> WholeNumber:
    log(f'Adding {lhs} and {rhs}...')
    log_indent()

    cache = [
        [0,  1,  2,  3,  4,  5,  6,  7,  8,  9],
        [1,  2,  3,  4,  5,  6,  7,  8,  9, 10],
        [2,  3,  4,  5,  6,  7,  8,  9, 10, 11],
        [3,  4,  5,  6,  7,  8,  9, 10, 11, 12],
        [4,  5,  6,  7,  8,  9, 10, 11, 12, 13],
        [5,  6,  7,  8,  9, 10, 11, 12, 13, 14],
        [6,  7,  8,  9, 10, 11, 12, 13, 14, 15],
        [7,  8,  9, 10, 11, 12, 13, 14, 15, 16],
        [8,  9, 10, 11, 12, 13, 14, 15, 16, 17],
        [9, 10, 11, 12, 13, 14, 15, 16, 17, 18]
    ]

    count = max(len(lhs.digits), len(rhs.digits))

    carryover_digit = None
    result = WholeNumber.from_int(0)
    for pos in range(0, count):  # from smallest to largest component
        log(f'Targeting {lhs._highlight(pos)} and {rhs._highlight(pos)}')
        log_indent()

        digit1 = lhs[pos]
        digit2 = rhs[pos]

        added = WholeNumber.from_int(cache[digit1.value][digit2.value])
        log(f'Using cache for initial add: {digit1} + {digit2} = {added}')

        if carryover_digit is not None:
            log(f'Using recursion for carryover add: {added} + {carryover_digit} = ...')
            added = added + WholeNumber.from_digit(carryover_digit)  # recurse -- this called __add__()
            carryover_digit = None

        if len(added) == 1:
            result[pos] = added[0]
        elif len(added) == 2:
            result[pos] = added[0]      # keep 1s digit
            carryover_digit = added[1]  # carryover 10s digit
        else:
            raise Exception('This should never happen')

        log(f'Result: {result._highlight(pos)}, Carryover: {carryover_digit}')
        log_unindent()

    if carryover_digit is not None:
        log(f'Remaining carryover: {lhs._highlight(count)}  [{carryover_digit}]')
        result[count] = carryover_digit
        log(f'Result: {result._highlight(count)}')

    log_unindent()
    log(f'Sum: {result}')

    return result

Subtraction

↩PREREQUISITES↩

The algorithm used by humans to subtract large whole numbers from each other is called vertical subtraction. Vertical subtraction relies on two ideas...

  1. Humans can easily subtract a small 1 to 2 digit numbers (anything smaller than 20) from each other without much effort. For example...

    ... are all subtraction operations that don't take much effort / are already probably cached in person's memory.

  2. Numbers represented in place-value notation can be broken down into single digit components -- the place of each digit in the number represents some portion of that number's value. For example, the number 935 can be broken down as 9 100s, 3 10s, and 5 1s...

    100
    100
    100
    100
    100            1
    100            1
    100     10     1
    100     10     1
    100     10     1
    ---     --     -
    900     30     5
    
    
    
    9 3 5
    │ │ │
    │ │ └─ ●
    │ │    ● 
    │ │    ● 
    │ │    ● 
    │ │    ● 
    │ │
    │ └─── ●●●●●●●●●●
    │      ●●●●●●●●●●
    │      ●●●●●●●●●●
    │
    └───── ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
           ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
           ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
           ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
           ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
           ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
           ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
           ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
           ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
    

Since a number can be broken down into single digit components and subtracting a single digit to any number is easy, any two numbers can be subtracted by subtracting their individual single digit components. For example, the number 53 and 21 are broken down as follows...

5 3                      2 1
│ │                      │ │
│ └─ ●                   │ └─ ●
│    ●                   │
│    ●                   └─── ●●●●●●●●●●
│                             ●●●●●●●●●●
└─── ●●●●●●●●●●
     ●●●●●●●●●●
     ●●●●●●●●●●
     ●●●●●●●●●●
     ●●●●●●●●●●

Subtract their individual single digit components from each other to get the difference. The ...

3 2
│ │
│ └─ ●
│    ● 
│
└─── ●●●●●●●●●●
     ●●●●●●●●●●
     ●●●●●●●●●●

In certain cases, the subtraction of two single digit components may not be possible. For example, subtracting 91 and 23...

9 1                      2 3
│ │                      │ │
│ └─ ●                   │ └─ ●
│                        │    ●
└─── ●●●●●●●●●●          │    ●
     ●●●●●●●●●●          │
     ●●●●●●●●●●          └─── ●●●●●●●●●●
     ●●●●●●●●●●               ●●●●●●●●●●
     ●●●●●●●●●●
     ●●●●●●●●●●
     ●●●●●●●●●●
     ●●●●●●●●●●
     ●●●●●●●●●●

The ...

The algorithm fails at the 1s place. It's impossible to remove 3 items from 1 item -- the most that can be removed from 1 item is 1 item. The way to handle this is to pick out 1 group from the 10s place and mover it over back to 1s place...

9 1                      2 3
│ │                      │ │
│ └─ ●                   │ └─ ●
│                        │    ●
└─── ●●●●●●●●●●          │    ●
     ●●●●●●●●●●          │
     ●●●●●●●●●●          └─── ●●●●●●●●●●
     ●●●●●●●●●●               ●●●●●●●●●●
     ●●●●●●●●●●
     ●●●●●●●●●●
     ●●●●●●●●●●
     ●●●●●●●●●●
    ┌──────────┐
    │●●●●●●●●●●│ each group is 10 items and we grabbed 1 of them (that's 10 items total)
    └──────────┘

move those items back to the 1s place

8 11                     2 3
│ │                      │ │
│ └─ ●                   │ └─ ●
|   ┌─┐                  │    ●
│   │●│                  │    ●
│   │●│                  │
│   │●│                  └─── ●●●●●●●●●●
│   │●│                       ●●●●●●●●●●
│   │●│                  
│   │●│
│   │●│
│   │●│
│   │●│
│   │●│
│   └─┘
│
└─── ●●●●●●●●●●
     ●●●●●●●●●●
     ●●●●●●●●●●
     ●●●●●●●●●●
     ●●●●●●●●●●
     ●●●●●●●●●●
     ●●●●●●●●●●
     ●●●●●●●●●●

Now it's possible to subtract. The ...

This process is called borrowing -- you're borrowing 1 group from the next largest position and moving those items back so that there's enough for subtraction to take place. In total, the value is still the same -- the total number of items (dots) doesn't change, but the items are being moved around so that the subtraction of a component can happen.

In certain cases, a group may need to be borrowed but the next largest position is 0. For example, subtracting 100 and 11...

1 0 0                      1 1
│ │ │                      │ │
│ │ └─ ●                   │ └─ ●
│ │                        │
│ └─── <empty>             └─── ●●●●●●●●●●
│
└───── ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●

Borrow recursively to handle this case:

The way to perform this algorithm in real-life is to stack the two numbers being subtracted on top of each other, where the positions for both numbers match up (e.g. the 1s position matches up, the 10s position matches up, the 100s position matched up, etc..). Then, subtract the individual single digit components together (from right-to-left). Every time borrowing is needed, cross out the number being changed and put the place their new numbers above. For example, subtracting 100 and 11 ...

10011\begin{alignedat}{3}{1}& \enspace{0}& \enspace{0}& \{ }& \enspace{1}& \enspace{1}& \enspace - \ \hline{ }& \enspace{ }& \enspace{ }&\end{alignedat}

The way to perform this algorithm via code is as follows...

arithmetic_code/WholeNumber.py (lines 287 to 374):

@log_decorator
def __sub__(lhs: WholeNumber, rhs: WholeNumber) -> WholeNumber:
    log(f'Subtracting {lhs} and {rhs}...')
    log_indent()

    sub_cache = [
        [0,    None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None],
        [1,    0,    None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None],
        [2,    1,    0,    None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None],
        [3,    2,    1,    0,    None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None],
        [4,    3,    2,    1,    0,    None, None, None, None, None, None, None, None, None, None, None, None, None, None, None],
        [5,    4,    3,    2,    1,    0,    None, None, None, None, None, None, None, None, None, None, None, None, None, None],
        [6,    5,    4,    3,    2,    1,    0,    None, None, None, None, None, None, None, None, None, None, None, None, None],
        [7,    6,    5,    4,    3,    2,    1,    0,    None, None, None, None, None, None, None, None, None, None, None, None],
        [8,    7,    6,    5,    4,    3,    2,    1,    0,    None, None, None, None, None, None, None, None, None, None, None],
        [9,    8,    7,    6,    5,    4,    3,    2,    1,    0,    None, None, None, None, None, None, None, None, None, None],
        [10,   9,    8,    7,    6,    5,    4,    3,    2,    1,    0,    None, None, None, None, None, None, None, None, None],
        [11,   10,   9,    8,    7,    6,    5,    4,    3,    2,    1,    0,    None, None, None, None, None, None, None, None],
        [12,   11,   10,   9,    8,    7,    6,    5,    4,    3,    2,    1,    0,    None, None, None, None, None, None, None],
        [13,   12,   11,   10,   9,    8,    7,    6,    5,    4,    3,    2,    1,    0,    None, None, None, None, None, None],
        [14,   13,   12,   11,   10,   9,    8,    7,    6,    5,    4,    3,    2,    1,    0,    None, None, None, None, None],
        [15,   14,   13,   12,   11,   10,   9,    8,    7,    6,    5,    4,    3,    2,    1,    0,    None, None, None, None],
        [16,   15,   14,   13,   12,   11,   10,   9,    8,    7,    6,    5,    4,    3,    2,    1,    0,    None, None, None],
        [17,   16,   15,   14,   13,   12,   11,   10,   9,    8,    7,    6,    5,    4,    3,    2,    1,    0,    None, None],
        [18,   17,   16,   15,   14,   13,   12,   11,   10,   9,    8,    7,    6,    5,    4,    3,    2,    1,    0,    None],
        [19,   18,   17,   16,   15,   14,   13,   12,   11,   10,   9,    8,    7,    6,    5,    4,    3,    2,    1,    0   ]
    ]

    # copy self because it may get modified during borrowing phase
    self_copy = lhs.copy()

    count = max(len(self_copy.digits), len(rhs.digits))

    result = WholeNumber.from_int(0)
    for pos in range(0, count):  # from smallest to largest component
        log(f'Targeting {self_copy._highlight(pos)} and {rhs._highlight(pos)}')
        log_indent()

        digit1 = self_copy[pos]
        digit2 = rhs[pos]
        result_digit = sub_cache[digit1.value][digit2.value]
        if result_digit is not None:
            log(f'Using cache for subtraction: {digit1} - {digit2} = {result_digit}')
        else:
            log('Not possible -- attempting to borrow')
            self_copy._borrow_from_next(sub_cache, pos)

            digit1 = self_copy[pos]
            digit2 = rhs[pos]
            result_digit = sub_cache[digit1.value][digit2.value]
            log(f'Using cache for subtraction: {digit1} - {digit2} = {result_digit}')

        result[pos] = result_digit
        log(f'Result: {result._highlight(pos)}')
        log_unindent()

    log_unindent()
    log(f'Difference: {result}')

    return result

@log_decorator
def _borrow_from_next(self: WholeNumber, sub_cache: List[List[int]], pos: int) -> None:
    if pos >= len(self):
        raise Exception('Not enough available to borrow')

    curr_digit = self[pos]
    next_digit = self[pos + 1]

    log(f'Borrowing from next largest {self._highlight(pos + 1)}')

    if next_digit == 0:
        log(f'Not possible -- attempting to borrow again')
        self._borrow_from_next(sub_cache, pos + 1)  # recursively borrow
        next_digit = self[pos + 1]  # updated because of borrow call above

    next_digit = sub_cache[next_digit.value][1]                             # sub 1 from next largest position
    curr_digit = (WholeNumber.from_int(10) + WholeNumber.from_digit(curr_digit))._as_digit()    # add 10 to current position

    # curr_digit is no longer an actual digit -- it's beyond the value of 9 (a digit is 0..9). We're using a
    # hack to get a out-of-bounds value as a digit because we need to subtract from it later on -- this is
    # trying to faithfully replicate the 'borrowing' logic in vertical subtraction

    self[pos + 1] = next_digit
    self[pos] = curr_digit

    log(f'Completed borrowing {self._highlight(pos, pos + 1)}')

Multiplication

↩PREREQUISITES↩

The algorithm used by humans to multiply large whole numbers together is called vertical multiplication. Vertical multiplication relies on three ideas...

  1. Humans have the ability to multiply a single digit number to another single digit number through memorization. For example...

    ... are all multiplication operations that can be done quickly if the person has cached the table below into their memory.

    * 0 1 2 3 4 5 6 7 8 9
    0 0 0 0 0 0 0 0 0 0 0
    1 0 1 2 3 4 5 6 7 8 9
    2 0 2 4 6 8 10 12 14 16 18
    3 0 3 6 9 12 15 18 21 24 27
    4 0 4 8 12 15 20 24 28 32 36
    5 0 5 10 15 20 25 30 35 40 45
    6 0 6 12 18 24 30 36 42 48 54
    7 0 7 14 21 28 35 42 49 56 63
    8 0 8 16 24 32 40 48 56 64 72
    9 0 9 18 27 36 45 54 63 72 81
  2. Numbers represented in place-value notation can be broken down into single digit components -- the place of each digit in the number represents some portion of that number's value. For example, the number 935 can be broken down as 9 100s, 3 10s, and 5 1s...

    100
    100
    100
    100
    100            1
    100            1
    100     10     1
    100     10     1
    100     10     1
    ---     --     -
    900     30     5
    
    
    
    9 3 5
    │ │ │
    │ │ └─ ●
    │ │    ● 
    │ │    ● 
    │ │    ● 
    │ │    ● 
    │ │
    │ └─── ●●●●●●●●●●
    │      ●●●●●●●●●●
    │      ●●●●●●●●●●
    │
    └───── ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
           ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
           ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
           ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
           ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
           ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
           ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
           ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
           ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
    
  3. If two numbers start with a single non-zero digit is followed by zero or more 0s, the result of their multiplication is equivalent to multiplying the single non-zero digits together and appending the 0s to the end. For example, ..

Any two numbers can be multiplied by ...

  1. breaking down each number into its single digit components (idea 2 above),
  2. then multiplying each component from the first number by each components from the second number (idea 1 and 3 above),
  3. then adding the results of those multiplications.

For example, the number 43 and 2 are broken down as follows...

4 3                      2
│ │                      │
│ └─ ●                   └─ ●
│    ●                      ●         
│    ●               
│                        
└─── ●●●●●●●●●●          
     ●●●●●●●●●●
     ●●●●●●●●●●
     ●●●●●●●●●●

Multiply their individual single digit components together results in ...

Add the results of the multiplications: 80 + 6 is 86. Note that 43 + 43 is also 86. Each multiplication above is giving back a portion of the final multiplication value, specifically a portion of a single digit component in the final multiplication value -- they need to be combined by adding.

8 6
│ │ ┌─┐
│ └─┤●│
│   │●│ 3        
│   │●│
│   ├─┤
│   │●│
│   │●│ 3
│   │●│
│   └─┘
│   ┌──────────┐
└───┤●●●●●●●●●●│          
    │●●●●●●●●●●│
    │●●●●●●●●●●│ 4
    │●●●●●●●●●●│
    ├──────────┤
    │●●●●●●●●●●│
    │●●●●●●●●●●│
    │●●●●●●●●●●│ 4
    │●●●●●●●●●●│
    └──────────┘

For another more complex example, the number 43 and 22 are broken down as follows...

4 3                      2 2
│ │                      │ │
│ └─ ●                   │ └─ ●
│    ●                   │    ●         
│    ●                   │              
│                        └─── ●●●●●●●●●●
└─── ●●●●●●●●●●               ●●●●●●●●●●
     ●●●●●●●●●●
     ●●●●●●●●●●
     ●●●●●●●●●●

Multiply their individual single digit components together results in ...

Add the results of the multiplications: 800 + 60 + 80 + 6 is 946. Note that 43 + 43 + 43 + 43 + 43 + 43 + 43 + 43 + 43 + 43 + 43 + 43 + 43 + 43 + 43 + 43 + 43 + 43 + 43 + 43 + 43 + 43 is also 946. Each multiplication above is giving back a portion of the final multiplication value, specifically a portion of a single digit component in the final multiplication value -- they need to be combined by adding.

The way to perform this algorithm in real-life is to stack the two numbers being multiplied on top of each other, where the positions for both numbers match up (e.g. the 1s position matches up, the 10s position matches up, the 100s position matched up, etc..). For example...

4322\begin{alignedat}{3}{ }& \enspace{4}& \enspace{3}& \{ }& \enspace{2}& \enspace{2}& \enspace * \ \hline{ }& \enspace{ }& \enspace{ }&\end{alignedat}

Then, for each component in the bottom number (from right-to-left), isolate to its single digit component and multiply by each component in the top number (from right-to-left). The answer for each digit of the bottom row is written underneath the answer prior to it. Starting from the first component of the bottom number...

Then, add the answers from each bottom iteration to get the final answer...

432286860+946\begin{alignedat}{3}{ }& \enspace{4}& \enspace{3}& \{ }& \enspace{2}& \enspace{2}& \enspace * \ \hline{ }& \enspace{8}& \enspace{6}& \{8}& \enspace{6}& \enspace{0}& \enspace + \ \hline{\green{9}}& \enspace{\green{4}}& \enspace{\green{6}}&\end{alignedat}

In many cases, multiplying 2 individual single digit components results in an extra digit (e.g. 7*7=49). If this happens, the bleed over digit is carried over to the next position (on the left). That is, the bleed over digit will get added to the result of the multiplication in the next position. This is denoted by stacking the bleed over digit on top of the next position. For example...

7777\begin{alignedat}{3}{ }& \enspace{7}& \enspace{7}& \{ }& \enspace{7}& \enspace{7}& \enspace * \ \hline{ }& \enspace{ }& \enspace{ }&\end{alignedat}

Then, add the answers from each bottom iteration to get the final answer...

5477875396160+6699\begin{alignedat}{4}{ }& \enspace{ }& \enspace{5}& \enspace{ }& \{ }& \enspace{ }& \enspace{4}& \enspace{ }& \{ }& \enspace{ }& \enspace{7}& \enspace{7}& \{ }& \enspace{ }& \enspace{8}& \enspace{7}& \enspace * \ \hline{ }& \enspace{5}& \enspace{3}& \enspace{9}& \{\green{6}}& \enspace{\green{1}}& \enspace{6}& \enspace{0}& \enspace + \ \hline{\green{6}}& \enspace{\green{6}}& \enspace{\green{9}}& \enspace{\green{9}}&\end{alignedat}

The way to perform this algorithm via code is as follows...

arithmetic_code/WholeNumber.py (lines 377 to 462):

@log_decorator
def __mul__(lhs: WholeNumber, rhs: WholeNumber) -> WholeNumber:
    log(f'Multiplying {lhs} and {rhs}...')
    log_indent()

    count = len(rhs.digits)

    res_list = []
    for pos in range(0, count):  # from smallest to largest component
        log(f'Targeting {lhs} and {rhs._highlight(pos)}')
        log_indent()

        self_copy = lhs.copy()    # create a copy
        self_copy.shift_left(pos)  # shift copy (add 0s) based on the digit we're on
        log(f'Appending 0s to multiplicand based on position of multiplier (pos {pos}): {self_copy} {rhs._highlight(pos)}')

        res = self_copy._single_digit_mul(rhs[pos])  # multiply copy by that digit
        log_unindent()

        res_list.append(res)

    log(f'Summing intermediate results to get final result...')
    log_indent()
    final_res = WholeNumber.from_int(0)
    for res in res_list:
        log(f'Adding {res} to {final_res}')
        final_res += res
    log_unindent()

    log_unindent()
    log(f'Product: {final_res}')

    return final_res

@log_decorator
def _single_digit_mul(self: WholeNumber, digit: Digit) -> WholeNumber:
    cache = [
        [0,  0,  0,  0,  0,  0,  0,  0,  0,  0 ],
        [0,  1,  2,  3,  4,  5,  6,  7,  8,  9 ],
        [0,  2,  4,  6,  8,  10, 12, 14, 16, 18],
        [0,  3,  6,  9,  12, 15, 18, 21, 24, 27],
        [0,  4,  8,  12, 16, 20, 24, 28, 32, 36],
        [0,  5,  10, 15, 20, 25, 30, 35, 40, 45],
        [0,  6,  12, 18, 24, 30, 36, 42, 48, 54],
        [0,  7,  14, 21, 28, 35, 42, 49, 56, 63],
        [0,  8,  16, 24, 32, 40, 48, 56, 64, 72],
        [0,  9,  18, 27, 36, 45, 54, 63, 72, 81]
    ]

    count = len(self.digits)

    carryover_digit = None
    result = WholeNumber.from_int(0)
    for pos in range(0, count):  # from smallest to largest component
        log(f'Targeting {self._highlight(pos)} and {digit}')
        log_indent()

        digit1 = self[pos]

        multed = WholeNumber.from_int(cache[digit1.value][digit.value])
        log(f'Using cache for initial mul: {digit1} * {digit} = {multed}')

        if carryover_digit is not None:
            adjusted_multed = multed + WholeNumber.from_digit(carryover_digit)
            log(f'Adding carryover: {multed} + {carryover_digit} = {adjusted_multed}')
            carryover_digit = None
            multed = adjusted_multed

        if len(multed) == 1:
            result[pos] = multed[0]
        elif len(multed) == 2:
            result[pos] = multed[0]      # keep 1s digit
            carryover_digit = multed[1]  # carryover 10s digit
        else:
            raise Exception('This should never happen')

        log(f'Result: {result._highlight(pos)}, Carryover: {carryover_digit}')
        log_unindent()

    if carryover_digit is not None:
        log(f'Remaining carryover: {self._highlight(count)}  [{carryover_digit}]')
        result[count] = carryover_digit
        log(f'Result: {result._highlight(count)}')

    return result

Division

↩PREREQUISITES↩

There are 2 algorithms used to divide large whole numbers:

These algorithms are detailed in the subsections below.

Trial and Error

↩PREREQUISITES↩

Trial-and-error division is an algorithm used for dividing numbers. The core idea behind the algorithm is that multiplication is the inverse of division. That is, multiplication reverses / un-does division (and vice-versa). For example...

Kroki diagram output

Knowing this, multiplication can be used to check if some number is the quotient. For example, to find the quotient for 20 / 5...

Kroki diagram output

5 * 4 = 20 -- If you have 5 groups of 4 items each, you'll have 20 items.

Kroki diagram output

Rather than testing each number incrementally, it's faster to start with a large test number and tweak its digits until the multiplication test passes. The algorithm maintains a pointer to a position in the test number which it uses to increment / decrement the digit at that position. Given a test number:

It continually does this until either the product matches the correct number or there are no more digits to tweak.

The core ideas behind this algorithm are:

  1. When comparing two test numbers, multiplying by the larger test number will result in a larger product.

  2. When comparing two test numbers, multiplying by the test number with more digits will result in a larger product.

For example, 2617 / 52...

Kroki diagram output

Starting with a test number of 100...

Since there are no more digits left, the quotient is 50 and the remainder is 17 (2617 - 2600 = 17).

In the example above, the starting test number of 100 was selected by taking advantage of a special property of whole number multiplication: the total number of digits in both inputs will equal to either ...

in1_len = len(input1.digits)
in2_len = len(input2.digits)
product_len = len(product.digits)

condition1 = in1_len + in2_len == product_len
condition2 = in1_len + in2_len == product_len + 1
assert condition1 or condition2

For example, ...

input1 input2 in1_len + in2_len == product_len in1_len + in2_len == product_len + 1
99 * 99 = 9801 99 99 True False
9 * 9 = 81 9 9 True False
1 * 9 = 9 1 9 False True

Given this property, the algorithm works backwards to calculate the maximum number of digits that input2's (the unknown input) whole part can be...

min_in2_len = product_len - in1_len
max_in2_len = product_len + 1 - in1_len

⚠️NOTE️️️⚠️

If you know algebra already, the way the code above was derive requires algebra. If you don't know algebra just take it at face value.

For example, ...

product_len - in1_len (min_in2_len) product_len - in1_len + 1 (max_in2_len)
99 * ? = 9801 2 3
9 * ? = 81 1 2
1 * ? = 9 0 1

The algorithm uses the maximum to pick a starting number: 1 followed by 0s...

max_in2_len input2_starting_test_num
99 * ? = 9801 3 100
9 * ? = 81 2 10
1 * ? = 9 1 1

In the main example above (52 * ? = 2617), the product has 4 digits and the known input has 2 digits, so a starting test number should of 3 digits was selected: 100.

⚠️NOTE️️️⚠️

This algorithm only performs quickly when a good starting test number is selected. For example, if the number 1 were selected as the starting test number for 52 * ? = 2617, the code will perform more steps than is necessary.

The trial-and-error division algorithm written as code is as follows:

arithmetic_code/WholeNumber.py (lines 511 to 633):

@staticmethod
@log_decorator
def choose_start_test_num_for_divte(input1: WholeNumber, expected_product: WholeNumber) -> WholeNumber:
    log(f'Choosing a starting test number to find {input1} \\* ? = {expected_product}...')
    log_indent()

    log(f'{input1} has {len(input1.digits)} digits')
    log(f'{expected_product}\'s has {len(expected_product.digits)} digits')
    num_of_zeros = len(expected_product.digits) - len(input1.digits)
    start_test_num = WholeNumber.from_str('1' + '0' * num_of_zeros)

    log(f'Starting test number: {start_test_num}')

    log_unindent()
    log(f'{start_test_num}')
    return start_test_num

@staticmethod
@log_decorator
def choose_start_modifier_for_divte(start_test_num: WholeNumber) -> WholeNumber:
    log(f'Choosing a starting modifier for {start_test_num}...')
    log_indent()

    log(f'{start_test_num} has {len(start_test_num.digits)} digits')
    num_of_zeros = len(start_test_num.digits) - 1
    start_modifier_num = WholeNumber.from_str('1' + '0' * num_of_zeros)

    log(f'Starting modifier: {start_modifier_num}')

    log_unindent()
    log(f'{start_modifier_num}')
    return start_modifier_num

@staticmethod
@log_decorator
def trial_and_error_div(dividend: WholeNumber, divisor: WholeNumber) -> (WholeNumber, WholeNumber):
    if divisor == WholeNumber.from_str('0'):
        raise Exception('Cannot divide by 0')

    log(f'Dividing {dividend} and {divisor}...')
    log_indent()

    log(f'Calculating starting test number...')
    test = WholeNumber.choose_start_test_num_for_divte(divisor, dividend)
    log(f'{test}')

    log(f'Calculating starting modifier for test number...')
    modifier = WholeNumber.choose_start_modifier_for_divte(test)
    log(f'{modifier}')

    class StepType(Enum):
        INCREMENTING = 0
        DECREMENTING = 1
        EQUAL = 2

    last_steptype = None
    while True:
        log(f'Testing {test}: {test} * {divisor}...')
        test_res = test * divisor
        log(f'{test_res}')

        log(f'Is {test_res} ==, >, or < to {dividend}? ...')
        log_indent()
        try:
            if test_res == dividend:
                last_steptype = StepType.EQUAL
                log(f'{test_res} == {dividend} -- Found')
                break
            elif test_res > dividend:
                last_steptype = StepType.DECREMENTING
                log(f'{test_res} > {dividend} -- Decrementing {test} by {modifier} until not >...')
                log_indent()
                while True:
                    log(f'Decrementing {test} by {modifier}...')
                    test -= modifier
                    log(f'{test} * {divisor}...')
                    modify_res = test * divisor
                    log(f'{modify_res}')
                    if not modify_res > dividend:
                        break
                log_unindent()
                log(f'Done: {test}')
            elif test_res < dividend:
                last_steptype = StepType.INCREMENTING
                log(f'{test_res} < {dividend} -- Incrementing {test} by {modifier} until not <...')
                log_indent()
                while True:
                    log(f'Incrementing {test} by {modifier}...')
                    test += modifier
                    log(f'{test} * {divisor}...')
                    modify_res = test * divisor
                    log(f'{modify_res}')
                    if not modify_res < dividend:
                        break
                log_unindent()
                log(f'Done: {test}')
        finally:
            log_unindent()

        if modifier == WholeNumber.from_str('1'):
            break

        log(f'Reducing modifier for next set of tests...')
        modifier = WholeNumber.from_str(str(modifier)[0:-1])
        log(f'{modifier}')

    # if the last set of tests were incrementing, the test number will be 1 more than where it needs to be moved
    # because the loop increments until it exceeds PAST the dividend
    if StepType.INCREMENTING == last_steptype:
        log(f'Decrementing test number (only happens if last set of tests were incrementing)...')
        if test * divisor > dividend:
            test -= WholeNumber.from_str('1')
        log(f'{test}')

    log (f'Determining remainder...')
    remainder = dividend - (test * divisor)
    log(f'{remainder}')

    log_unindent()
    log(f'Quotient: {test}, Remainder: {remainder}')

    return test, remainder

Long Division

↩PREREQUISITES↩

The algorithm used by humans to divide large whole numbers is called long division. In most cases, it can divide a number in less steps than trial-and-error division. Long division relies on three ideas...

  1. Numbers represented in place-value notation can be broken down into single digit components -- the place of each digit in the number represents some portion of that number's value. For example, the number 935 can be broken down as 9 100s, 3 10s, and 5 1s...

    100
    100
    100
    100
    100            1
    100            1
    100     10     1
    100     10     1
    100     10     1
    ---     --     -
    900     30     5
    
    
    
    9 3 5
    │ │ │
    │ │ └─ ●
    │ │    ● 
    │ │    ● 
    │ │    ● 
    │ │    ● 
    │ │
    │ └─── ●●●●●●●●●●
    │      ●●●●●●●●●●
    │      ●●●●●●●●●●
    │
    └───── ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
           ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
           ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
           ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
           ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
           ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
           ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
           ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
           ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
    
  2. Any number can be divided using trial-and-error division. For example, 20 / 5...

    Kroki diagram output

  3. When dividing, if the number being divided (dividend) has trailing zeros, those trailing zeros can be removed prior to the division and then put back on after the division. For example, 4500 / 6...

    Kroki diagram output

    When 4500 items are broken up into groups of 6, this rule says that there will be at least 700 groups. 300 of the 4500 items remain unaccounted for, but the rule can be used again on these 300 items because 300 has trailing 0s (recursive).

    ⚠️NOTE️️️⚠️

    It's easy to test if this is correct...

    ⚠️NOTE️️️⚠️

    The reasoning behind why trailing 0s can be removed and re-appended has to do with expressions / order of operations / factoring. Taking the original 4500 / 7 example above...

    • 4500 / 7
    • (45 * 100) / 7 <-- factor out 100 from the 4500
    • 45 * 100 / 7 <-- remove parenthesis, associativity law, mult and div have same precedence so it doesn't matter which gets performed first
    • 45 / 7 * 100 <-- swap, commutative law, mult and div have same precedence so it doesn't matter which gets performed first
    • (45 / 7) * 100
    • (7R3) * 100
    • 700R300

    In certain cases, the quotient returned by the operation will end up being 0. This means that the operation failed.

    If this happens, less trialing-zeros need to be stripped-off. Keep leaving in trialing 0s and re-doing the operation until the quotient becomes non-zero. For example, when all 3 trailing 0s are stripped from 4000 / 6...

    Kroki diagram output

    ... the quotient is 0 and the remainder is 4000. The operation pretty much failed because the amount of remaining items is the same as the amount starting amount -- nothing was grouped and everything remains. As such, more trialing 0s need to be left in. Re-try the operation with only 2 trialing 0s removed...

    Kroki diagram output

    ... the quotient is 600 and the remainder is 400. When 4000 items are broken up into groups of 6, there will be at least 600 groups. 400 of the 4000 items remain unaccounted for, but the rule can be used again on these 400 items because 400 has trailing 0s (recursive).

The idea behind long division is to break up the dividend into its individual single digit components results (idea 1) and divide each component by the divisor. For example, 752 / 3...

Kroki diagram output

Each of the divisions are easy to perform because trialing 0s can be stripped-off prior to trial-and-error division (ideas 2 and 3). That is, the actual numbers being input into trial-and-error division are much smaller than they would normally be because trailing 0s are removed. Smaller numbers mean easier to perform.

Kroki diagram output

⚠️NOTE️️️⚠️

The TE block is applying idea 3. The trialing 0s are being stripped off, trial-and-error division is being performed, then the 0s are re-append to the quotient and the remainder.

The remainders need to be accounted for. That is, if there are enough remaining items to form a group, they should be grouped. The process is repeated on the remaining items until there aren't enough to form a group (until the remainder is less than the divisor). Once there aren't enough remaining items to form a group, the sum of the quotients becomes the final quotient (final number of groups) and the remainder becomes the final remainder...

⚠️NOTE️️️⚠️

The diagram below looks daunting but it's just 3 copies of the diagrams above stacked on top of each other -- 1 for each iteration. The remainders from each iteration are being combined and used as the input for the next iteration. The quotients from each iteration are being combined to get the total quotient (total number of groups).

The diagram is intended to be an intermediary step to reasoning about long division. There's further simplification / explanation after it.

Kroki diagram output

The answer to 752 / 3 is 250R2.

⚠️NOTE️️️⚠️

You can confirm this by doing 250 * 3 then adding 2. The result should be 752.

This process can be made much simpler by focusing on one component at a time. Starting from the largest component to the smallest component, divide (using idea 3) but then roll-in (add) the remainder into the next component. The thought process is exactly the same as above -- the division is being performed on a component and the remaining items from that division are being accounted for because they're being added to the next component (which gets divided next). For example, 752 / 3...

⚠️NOTE️️️⚠️

Notice how the inputs to TE still have trailing 0s.

  1. Divide the largest component (700)...

    Kroki diagram output

  2. Roll in remainder to the second largest component (50) and divide...

    Kroki diagram output

  3. Roll in remainder to the third largest component (2) and divide...

    Kroki diagram output

  4. The sum of the quotients becomes the final quotient, and the last remainder becomes the final remainder...

    Kroki diagram output

This is effectively the algorithm that humans use for long division -- for each component, divide (using idea 3) and roll in the remainder to the next component. Repeat the process until there are no components remaining.

The notation used by humans for long division is...

divisor)quotientdivisor)dividend\begin{array}{l}\phantom{{{divisor}\smash{)}}}{{quotient}} \{{divisor}}\overline{\smash{)}{dividend}} \\end{array}

For example, long division notation for 752 / 3 is initially written as...

3)3)752\begin{array}{l}\phantom{{{3}\smash{)}}}{{}} \{{3}}\overline{\smash{)}{752}} \\end{array}

Starting with the first component, divide (using idea 3) to get the quotient and remainder for that component: 200R100. Then, strip-off the trialing 0s and place the quotient on-top of the component and the remainder below the component...

3)23)7523)?3)1\begin{array}{l}\phantom{{{3}\smash{)}}}{{\green{2}}} \{{3}}\overline{\smash{)}{752}} \\phantom{{{3}\smash{)}}}{?} \\phantom{{{3}\smash{)}}}{\green{1}} \\end{array}

A question mark is sandwiched between the component and remainder. The question mark should be set to the value of the divisor (3) multiplied by the quotient (200), with its trailing 0s stripped out. 3 * 200 = 600, strip the trialing 0s to get 6...

3)23)7523)63)1\begin{array}{l}\phantom{{{3}\smash{)}}}{{2}} \{{3}}\overline{\smash{)}{752}} \\phantom{{{3}\smash{)}}}{\underline{\green{6}}} \\phantom{{{3}\smash{)}}}{1} \\end{array}

⚠️NOTE️️️⚠️

The traditional way this is stated when being taught in school is "how many times can 7 go into 3?". Essentially, find the minimum number that the quotient can be without exceeding the component.

3)23)752\begin{array}{l}\phantom{{{3}\smash{)}}}{{2}} \{{3}}\overline{\smash{)}{752}} \\end{array}

Put the answer to 3*2 = 6 underneath the component, then subtract to get the remainder...

3)23)7523)63)1\begin{array}{l}\phantom{{{3}\smash{)}}}{{2}} \{{3}}\overline{\smash{)}{752}} \\phantom{{{3}\smash{)}}}{\underline{6}} \\phantom{{{3}\smash{)}}}{1} \\end{array}

Copy the next largest component down such that it's next the remainder...

3)23)7523)63)15\begin{array}{l}\phantom{{{3}\smash{)}}}{{2}} \{{3}}\overline{\smash{)}{752}} \\phantom{{{3}\smash{)}}}{\underline{6}} \\phantom{{{3}\smash{)}}}{1\green{5}} \\end{array}

This is effectively the same as adding the remainder to the next component: 100 + 50 = 150. Trailing 0s aren't seen because they're implied in long division notation.

⚠️NOTE️️️⚠️

The traditional way this is stated when being taught in school is "drag down the next component".

Repeat the process but target the 15 at the bottom. The 15 is the next component rolled into the remainder...

3)253)7523)63)153)153)00\begin{array}{l}\phantom{{{3}\smash{)}}}{{2\green{5}}} \{{3}}\overline{\smash{)}{752}} \\phantom{{{3}\smash{)}}}{\underline{6}} \\phantom{{{3}\smash{)}}}{15} \\phantom{{{3}\smash{)}}}{\underline{\green{15}}} \\phantom{{{3}\smash{)}}}{\phantom{0}\green{0}} \\end{array}

Copy the next largest component down such that it's next the remainder...

3)253)7523)63)153)153)002\begin{array}{l}\phantom{{{3}\smash{)}}}{{25}} \{{3}}\overline{\smash{)}{752}} \\phantom{{{3}\smash{)}}}{6} \\phantom{{{3}\smash{)}}}{15} \\phantom{{{3}\smash{)}}}{15} \\phantom{{{3}\smash{)}}}{\phantom{0}0\green{2}} \\end{array}

Repeat the entire process but target the 2 at the bottom. The 2 is the next component rolled into the remainder...

3)2503)7523)63)153)153)0023)0003)002\begin{array}{l}\phantom{{{3}\smash{)}}}{{25\green{0}}} \{{3}}\overline{\smash{)}{752}} \\phantom{{{3}\smash{)}}}{\underline{6}} \\phantom{{{3}\smash{)}}}{15} \\phantom{{{3}\smash{)}}}{\underline{15}} \\phantom{{{3}\smash{)}}}{\phantom{0}02} \\phantom{{{3}\smash{)}}}{\phantom{00}\underline{\green{0}}} \\phantom{{{3}\smash{)}}}{\phantom{00}\green{2}} \\end{array}

The final reminder isn't 0, so place it next to the final quotient...

3)250R23)7523)63)153)153)0023)0003)002\begin{array}{l}\phantom{{{3}\smash{)}}}{{250\green{R2}}} \{{3}}\overline{\smash{)}{752}} \\phantom{{{3}\smash{)}}}{\underline{6}} \\phantom{{{3}\smash{)}}}{15} \\phantom{{{3}\smash{)}}}{\underline{15}} \\phantom{{{3}\smash{)}}}{\phantom{0}02} \\phantom{{{3}\smash{)}}}{\phantom{00}\underline{0}} \\phantom{{{3}\smash{)}}}{\phantom{00}2} \\end{array}

The way to perform this algorithm via code is as follows...

arithmetic_code/WholeNumber.py (lines 465 to 508):

@log_decorator
def __truediv__(dividend: WholeNumber, divisor: WholeNumber) -> (WholeNumber, WholeNumber):
    if divisor == WholeNumber.from_int(0):
        raise Exception('Cannot divide by 0')

    log(f'Dividing {dividend} by {divisor}...')
    log_indent()

    count = len(dividend.digits)

    quot = WholeNumber.from_int(0)
    rem = WholeNumber.from_int(0)
    for pos in reversed(range(0, count)):  # from largest to smallest component
        log(f'Targeting dividend: {dividend._highlight(pos)}, Current quotient: {quot} / Current remainder: {rem}')
        log_indent()

        comp = dividend[pos]
        if pos == count - 1:  # if this is the start component (largest component)...
            comp_dividend = WholeNumber.from_digit(comp)
            log(f'Set dividend: component ({comp}): {comp_dividend}')
        else:
            temp_rem = rem.copy()
            temp_rem.shift_left(1)
            comp_dividend = WholeNumber.from_digit(comp) + temp_rem
            log(f'Set dividend: Combining prev remainder ({rem}) with component ({comp}): {comp_dividend}')

        comp_quot, comp_rem = WholeNumber.trial_and_error_div(comp_dividend, divisor)
        log(f'Trial-and-error division: {comp_dividend} / {divisor} = {comp_quot}R{comp_rem}')

        new_quot = quot.copy()
        new_quot.shift_left(1)
        new_quot[0] = comp_quot[0]  # comp_quot will always be a single digit
        log(f'New quotient: Combining existing quotient ({quot}) with ({comp_quot}): {new_quot}')
        log(f'New remainder: {comp_rem}')
        quot = new_quot
        rem = comp_rem

        log_unindent()

    log_unindent()
    log(f'Final Quotient: {quot}, Final Remainder: {rem}')

    return quot, rem

Word Conversion

Whole number word conversion is the process of taking a whole number and converting it to words. To convert a whole number to words, break up the number into groups of 3 from least-significant digit to most-significant digit (right-to-left). For example, the number 9876543210 gets broken up as follows...

Kroki diagram output

For each group, use the following algorithm to construct the words to represent that group:

In the example above, each group would get converted as follows...

Kroki diagram output

The words for each group get a special suffix. For each group from right-to-left, ...

Group Word
1
2 thousand
3 million
4 billion
5 trillion
... ...

In the example above, each group would get its corresponding suffix added...

Kroki diagram output

There is one special case with number to word conversions: if the number being converted is 0, the output should be zero.

Kroki diagram output

The way to perform this algorithm via code is as follows...

arithmetic_code/WholeNumber.py (lines 718 to 850):

@log_decorator
def to_words(self: WholeNumber) -> str:
    suffixes = [None, 'thousand', 'million', 'billion', 'trillion', 'quadrillion', 'quintillion']

    log(f'Converting {self}...')
    log_indent()

    output = ''

    digits_copy = self.digits[:]
    while not digits_copy == []:
        d1 = digits_copy.pop(0) if digits_copy != [] else None
        d2 = digits_copy.pop(0) if digits_copy != [] else None
        d3 = digits_copy.pop(0) if digits_copy != [] else None

        log(f'Converting group {d3} {d2} {d1}...')
        log_indent()

        txt = ''
        if d3 is not None and d3 != Digit(0):
            if d3.value == Digit(1):
                txt += 'one hundred'
            elif d3.value == Digit(2):
                txt += 'two hundred'
            elif d3.value == Digit(3):
                txt += 'three hundred'
            elif d3.value == Digit(4):
                txt += 'four hundred'
            elif d3.value == Digit(5):
                txt += 'five hundred'
            elif d3.value == Digit(6):
                txt += 'six hundred'
            elif d3.value == Digit(7):
                txt += 'seven hundred'
            elif d3.value == Digit(8):
                txt += 'eight hundred'
            elif d3.value == Digit(9):
                txt += 'nine hundred'
            else:
                raise Exception()

        ignore_first_digit = False
        if d2 is not None and d3 != Digit(0):
            txt += ' '
            if d2.value == Digit(1):
                ignore_first_digit = True
                if d1 == Digit(0):
                    txt += 'ten'
                elif d1 == Digit(1):
                    txt += 'eleven'
                elif d1 == Digit(2):
                    txt += 'twelve'
                elif d1 == Digit(3):
                    txt += 'thirteen'
                elif d1 == Digit(4):
                    txt += 'fourteen'
                elif d1 == Digit(5):
                    txt += 'fifteen'
                elif d1 == Digit(6):
                    txt += 'sixteen'
                elif d1 == Digit(7):
                    txt += 'seventeen'
                elif d1 == Digit(8):
                    txt += 'eighteen'
                elif d1 == Digit(9):
                    txt += 'nineteen'
                else:
                    raise Exception()
            elif d2.value == Digit(2):
                txt += 'twenty'
            elif d2.value == Digit(3):
                txt += 'thirty'
            elif d2.value == Digit(4):
                txt += 'forty'
            elif d2.value == Digit(5):
                txt += 'fifty'
            elif d2.value == Digit(6):
                txt += 'sixty'
            elif d2.value == Digit(7):
                txt += 'seventy'
            elif d2.value == Digit(8):
                txt += 'eighty'
            elif d2.value == Digit(9):
                txt += 'ninety'
            else:
                raise Exception()

        if not ignore_first_digit and d1 is not None and d1 != Digit(0):
            txt += ' '
            if d1.value == Digit(1):
                txt += 'one'
            elif d1.value == Digit(2):
                txt += 'two'
            elif d1.value == Digit(3):
                txt += 'three'
            elif d1.value == Digit(4):
                txt += 'four'
            elif d1.value == Digit(5):
                txt += 'five'
            elif d1.value == Digit(6):
                txt += 'six'
            elif d1.value == Digit(7):
                txt += 'seven'
            elif d1.value == Digit(8):
                txt += 'eight'
            elif d1.value == Digit(9):
                txt += 'nine'
            else:
                raise Exception()

        if suffixes == []:
            raise Exception('Number too large')

        log(f'Words: {txt}')

        suffix = suffixes.pop(0)
        if suffix is not None:
            txt += ' ' + suffix

        log(f'Suffix: {suffix}')
        log_unindent()

        output = txt + ' ' + output

    output = output.lstrip()
    if output == '':
        output = 'zero'

    log_unindent()
    log(f'{output}')

    return output.strip()

Integer Number

↩PREREQUISITES↩

Kroki diagram output

Integer numbers are place-value notation numbers that have no fractional part but are mirrored across 0. That is, think of integers as 2 sets of counting numbers separated by 0, where everything to the...

Kroki diagram output

⚠️NOTE️️️⚠️

The word ...

The prefix that determines if a integer is positive or negative is referred to as the sign. All numbers other than 0 have a sign. 0 represents nothing / no value, which is why it doesn't have a sign -- it's used as a separation point between the positive and negative values.

⚠️NOTE️️️⚠️

If a number (other than 0) is positive, the + sign is typically left out. So, ...

Conceptually, you can think of the positives the same way you think about natural numbers. They represent some value. For each positive, there's a corresponding negative that represents the opposite of that positive value. For example, if...

Equality

↩PREREQUISITES↩

Integer equality is an extension of whole number equality. In whole number equality, the digit at each position must match between the numbers being compared. Integer equality adds an extra stipulation: the sign of the number must match as well.

For example, the numbers -195 and 195 are not equal...

- 1 9 5
x | | |
+ 1 9 5

... while the numbers -195 and -195 are equal...

- 1 9 5
| | | |
- 1 9 5

The way to perform this algorithm via code is as follows...

arithmetic_code/IntegerNumber.py (lines 211 to 229):

@log_decorator
def __eq__(self: IntegerNumber, other: IntegerNumber) -> bool:
    log(f'Equality testing {self} and {other}...')
    log_indent()

    log(f'Testing sign equality ({self.sign} vs {other.sign})...')
    sign_eq = self.sign == other.sign
    log(f'{sign_eq}')

    log(f'Testing magnitude equality ({self.magnitude} vs {other.magnitude})...')
    mag_eq = self.magnitude == other.magnitude
    log(f'{mag_eq}')

    log_unindent()
    ret = sign_eq and mag_eq
    log(f'{ret}')

    return ret

Less Than

↩PREREQUISITES↩

Recall that the number line for integers is more complex than the number line for whole numbers. The negatives and positives mirror at 0 and they grow in opposite directions:

Kroki diagram output

The algorithm for integer less than applies different logic depending on the sign of each number. Specifically, if the numbers are...

The way to perform this algorithm via code is as follows...

arithmetic_code/IntegerNumber.py (lines 232 to 263):

@log_decorator
def __lt__(self: IntegerNumber, other: IntegerNumber) -> bool:
    log(f'Less than testing {self} and {other}...')
    log_indent()

    self_sign = self.sign
    if self_sign is None:  # assume 0 is a positive -- it simplifies logic below
        self_sign = Sign.POSITIVE

    other_sign = other.sign
    if other_sign is None:  # assume 0 is a positive -- it simplifies logic below
        other_sign = Sign.POSITIVE

    if self_sign == Sign.POSITIVE and other_sign == Sign.POSITIVE:
        log(f'{self.sign} < {other.sign}: Applying whole number less than...')
        ret = self.magnitude < other.magnitude
    elif self_sign == Sign.NEGATIVE and other_sign == Sign.NEGATIVE:
        log(f'{self.sign} < {other.sign}: Turning positive and applying whole number greater than...')
        ret = self.magnitude > other.magnitude
    elif self_sign == Sign.POSITIVE and other_sign == Sign.NEGATIVE:
        log(f'{self.sign} < {other.sign}:: Different signs -- number being tested is positive...')
        ret = False
    elif self_sign == Sign.NEGATIVE and other_sign == Sign.POSITIVE:
        log(f'{self.sign} < {other.sign}: Different signs -- number being tested is negative...')
        ret = True
    log(f'{ret}')

    log_unindent()
    log(f'{ret}')

    return ret

Greater Than

↩PREREQUISITES↩

Recall that the number line for integers is more complex than the number line for whole numbers. The negatives and positives mirror at 0 and they grow in opposite directions:

Kroki diagram output

The algorithm for integer greater than applies different logic depending on the sign of each number. Specifically, if the numbers are...

The way to perform this algorithm via code is as follows...

arithmetic_code/IntegerNumber.py (lines 269 to 300):

@log_decorator
def __gt__(self: IntegerNumber, other: IntegerNumber) -> bool:
    log(f'Greater than testing {self} and {other}...')
    log_indent()

    self_sign = self.sign
    if self_sign is None:  # assume 0 is a positive -- it simplifies logic below
        self_sign = Sign.POSITIVE

    other_sign = other.sign
    if other_sign is None:  # assume 0 is a positive -- it simplifies logic below
        other_sign = Sign.POSITIVE

    if self_sign == Sign.POSITIVE and other_sign == Sign.POSITIVE:
        log(f'{self.sign} > {other.sign}: Applying whole number less than...')
        ret = self.magnitude > other.magnitude
    elif self_sign == Sign.NEGATIVE and other_sign == Sign.NEGATIVE:
        log(f'{self.sign} > {other.sign}: Turning positive and applying whole number greater than...')
        ret = self.magnitude < other.magnitude
    elif self_sign == Sign.POSITIVE and other_sign == Sign.NEGATIVE:
        log(f'{self.sign} > {other.sign}:: Different signs -- number being tested is positive...')
        ret = True
    elif self_sign == Sign.NEGATIVE and other_sign == Sign.POSITIVE:
        log(f'{self.sign} > {other.sign}: Different signs -- number being tested is negative...')
        ret = False
    log(f'{ret}')

    log_unindent()
    log(f'{ret}')

    return ret

Addition

↩PREREQUISITES↩

Conceptually, you can think of integer addition as movement on a number line. If some integer is being added to a...

The algorithm used by humans to add integer numbers together revolves around inspecting the sign and magnitude of each integer, then deciding whether to perform whole number addition or whole number subtraction to get the result. The codification of this algorithm is as follows...

arithmetic_code/IntegerNumber.py (lines 50 to 82):

@log_decorator
def __add__(lhs: IntegerNumber, rhs: IntegerNumber) -> IntegerNumber:
    log(f'Adding {lhs} and {rhs}')
    log_indent()

    def determine_sign(magnitude: WholeNumber, default_sign: Sign) -> Sign:
        if magnitude == WholeNumber.from_int(0):
            return None
        else:
            return default_sign

    if lhs.sign is None:  # sign of None is only when magnitude is 0,  0 + a = a
        sign = rhs.sign
        magnitude = rhs.magnitude
    elif rhs.sign is None:  # sign of None is only when magnitude is 0,  a + 0 = a
        sign = lhs.sign
        magnitude = lhs.magnitude
    elif lhs.sign == rhs.sign:
        magnitude = lhs.magnitude + rhs.magnitude
        sign = determine_sign(magnitude, lhs.sign)
    elif lhs.sign != rhs.sign:
        if rhs.magnitude >= lhs.magnitude:
            magnitude = rhs.magnitude - lhs.magnitude
            sign = determine_sign(magnitude, rhs.sign)
        else:
            magnitude = lhs.magnitude - rhs.magnitude
            sign = determine_sign(magnitude, lhs.sign)

    log_unindent()
    log(f'sign: {sign}, magnitude: {magnitude}')

    return IntegerNumber(sign, magnitude)

Subtraction

↩PREREQUISITES↩

Conceptually, you can think of integer subtraction as movement on a number line (opposite movement to that of integer addition). If the integer being subtracted by (right-hand side) is a...

The algorithm used by humans to subtract integer numbers revolves around inspecting the sign and magnitude of each integer, then deciding whether to perform whole number addition or whole number subtraction to get the result. The codification of this algorithm is as follows...

arithmetic_code/IntegerNumber.py (lines 85 to 123):

@log_decorator
def __sub__(lhs: IntegerNumber, rhs: IntegerNumber) -> IntegerNumber:
    log(f'Subtracting {lhs} and {rhs}')
    log_indent()

    def determine_sign(magnitude: WholeNumber, default_sign: Sign) -> Sign:
        if magnitude == WholeNumber.from_int(0):
            return None
        else:
            return default_sign

    def flip_sign(sign: Sign) -> Sign:
        if sign == Sign.POSITIVE:
            return Sign.NEGATIVE
        elif sign == Sign.NEGATIVE:
            return Sign.POSITIVE

    if lhs.sign is None:  # sign of None is only when magnitude is 0,  0 - a = -a
        sign = flip_sign(rhs.sign)
        magnitude = rhs.magnitude
    elif rhs.sign is None:  # sign of None is only when magnitude is 0,  a - 0 = a
        sign = lhs.sign
        magnitude = lhs.magnitude
    elif lhs.sign == rhs.sign:
        if rhs.magnitude >= lhs.magnitude:
            magnitude = rhs.magnitude - lhs.magnitude
            sign = determine_sign(magnitude, flip_sign(lhs.sign))
        else:
            magnitude = lhs.magnitude - rhs.magnitude
            sign = determine_sign(magnitude, lhs.sign)
    elif lhs.sign != rhs.sign:
        magnitude = lhs.magnitude + rhs.magnitude
        sign = determine_sign(magnitude, lhs.sign)

    log_unindent()
    log(f'sign: {sign}, magnitude: {magnitude}')

    return IntegerNumber(sign, magnitude)

Multiplication

↩PREREQUISITES↩

Conceptually, you can think of integer multiplication as repetitive integer addition / integer subtraction. When the right hand side is negative, think of it as subtraction instead of addition. For example, think of ...

One useful property of integer multiplication is that, multiplying any non-zero number by -1 will slip its sign. For example...

The algorithms humans use to perform integer multiplication is as follows:

  1. Ignoring the sign and multiply the numbers using whole number multiplication.
  2. If the sign are...
    1. the same, make the result a positive.
    2. different, make the result a negative.

The result produced using the algorithm will be exactly the same as the result produced using repetitive addition/subtraction.

The way to perform this algorithm via code is as follows...

arithmetic_code/IntegerNumber.py (lines 126 to 156):

@log_decorator
def __mul__(lhs: IntegerNumber, rhs: IntegerNumber) -> IntegerNumber:
    log(f'Multiplying {lhs} and {rhs}')
    log_indent()

    def determine_sign(magnitude: WholeNumber, default_sign: Sign) -> Sign:
        if magnitude == WholeNumber.from_int(0):
            return None
        else:
            return default_sign

    if lhs.sign is None:  # when sign isn't set, magnitude is always 0 -- 0 * a = 0
        sign = None
        magnitude = WholeNumber.from_int(0)
    elif rhs.sign is None:  # when sign isn't set, magnitude is always 0 -- a * 0 = 0
        sign = None
        magnitude = WholeNumber.from_int(0)
    elif (lhs.sign == Sign.POSITIVE and rhs.sign == Sign.POSITIVE) \
            or (lhs.sign == Sign.NEGATIVE and rhs.sign == Sign.NEGATIVE):
        magnitude = lhs.magnitude * rhs.magnitude
        sign = determine_sign(magnitude, Sign.POSITIVE)
    elif (lhs.sign == Sign.POSITIVE and rhs.sign == Sign.NEGATIVE) \
            or (lhs.sign == Sign.NEGATIVE and rhs.sign == Sign.POSITIVE):
        magnitude = lhs.magnitude * rhs.magnitude
        sign = determine_sign(magnitude, Sign.NEGATIVE)

    log_unindent()
    log(f'sign: {sign}, magnitude: {magnitude}')

    return IntegerNumber(sign, magnitude)

Division

↩PREREQUISITES↩

Conceptually, you can think of integer division the same as whole number division: repetitive integer subtraction -- how many iterations can be subtracted until reaching 0. When both numbers being divided have the same sign, the process is nearly the same as whole number division. For example, ...

When the sign are different, it becomes slightly more difficult to conceptualize. For example, using repetitive subtraction on -15 / 3 will get farther from 0 rather than closer:

  1. -15 - 3 = -18
  2. -18 - 3 = -21
  3. -21 - 3 = -24
  4. ...

In cases such as this, the concept of negative iterations is needed. For example, when ...

Why? The inverse (opposite) of subtraction is addition. Performing -5 iterations means doing the opposite for 5 iterations.

⚠️NOTE️️️⚠️

Remember that for integer numbers, a negative integer is one that's the mirror opposite of the positive (and vice versa).

The algorithms humans use to perform integer multiplication is as follows:

  1. Ignoring the sign and divide the numbers using whole number division.
  2. If the sign are...
    1. the same, make the result a positive.
    2. different, make the result a negative.

The result produced using the algorithm will be exactly the same as the result produced using repetitive subtraction.

The way to perform this algorithm via code is as follows...

arithmetic_code/IntegerNumber.py (lines 159 to 192):

@log_decorator
def __truediv__(lhs: IntegerNumber, rhs: IntegerNumber) -> (IntegerNumber, IntegerNumber):
    log(f'Dividing {lhs} and {rhs}')
    log_indent()

    def determine_sign(magnitude: WholeNumber, default_sign: Sign) -> Sign:
        if magnitude == WholeNumber.from_int(0):
            return None
        else:
            return default_sign

    if lhs.sign is None:  # when sign isn't set, magnitude is always 0 -- 0 / a = 0
        (quotient_magnitude, remainder_magnitude) = lhs.magnitude / rhs.magnitude
        quotient_sign = None
        remainder_sign = None
    elif rhs.sign is None:  # when sign isn't set, magnitude is always 0 -- a / 0 = err
        raise Exception('Cannot divide by 0')
    elif (lhs.sign == Sign.POSITIVE and rhs.sign == Sign.POSITIVE) \
            or (lhs.sign == Sign.NEGATIVE and rhs.sign == Sign.NEGATIVE):
        (quotient_magnitude, remainder_magnitude) = lhs.magnitude / rhs.magnitude
        quotient_sign = determine_sign(quotient_magnitude, Sign.POSITIVE)
        remainder_sign = determine_sign(remainder_magnitude, Sign.POSITIVE)
    elif (lhs.sign == Sign.POSITIVE and rhs.sign == Sign.NEGATIVE) \
            or (lhs.sign == Sign.NEGATIVE and rhs.sign == Sign.POSITIVE):
        (quotient_magnitude, remainder_magnitude) = lhs.magnitude / rhs.magnitude
        quotient_sign = determine_sign(quotient_magnitude, Sign.NEGATIVE)
        remainder_sign = determine_sign(remainder_magnitude, Sign.NEGATIVE)

    log_unindent()
    log(f'QUOTIENT: sign: {quotient_sign}, magnitude: {quotient_magnitude}')
    log(f'REMAINDER: sign: {remainder_sign}, magnitude: {remainder_magnitude}')

    return IntegerNumber(quotient_sign, quotient_magnitude), IntegerNumber(remainder_sign, remainder_magnitude)

Word Conversion

↩PREREQUISITES↩

Integer word conversion is the process of taking an integer number and converting it to words. The algorithm used by humans to convert an integer number to words is as follows:

Begin by converting the sign to a word. If the number is ...

Kroki diagram output

⚠️NOTE️️️⚠️

  1. It's acceptable to use the word "positive" when the sign is positive (recall 0 is neither positive nor negative).
  2. It's acceptable to use the word "minus" instead of "negative." However, doing so may introduce ambiguity if the words are being used in the context of subtraction because minus also means subtraction.

Then, write out the actual number as you would during whole number word conversion.

Kroki diagram output

For example, the number...

The way to perform this algorithm via code is as follows...

arithmetic_code/IntegerNumber.py (lines 195 to 208):

@log_decorator
def to_words(self: IntegerNumber) -> str:
    log(f'Converting {self}...')

    output = ''
    if self.sign == Sign.NEGATIVE:
        output += 'negative '
    output += self.magnitude.to_words()

    log_unindent()
    log(f'{output}')

    return output.lstrip()

Multiple

↩PREREQUISITES↩

Imagine that you have the integer numbers n and m (use the letters as placeholders for some arbitrary integer numbers). m is a multiple of n if some integer exists such that n?=mn \cdot ? = m.

For example, the multiples of 2 are...

A number like 7 wouldn't be a multiple of 2 because there is no integer that can be multiplied by 2 to get 7 -- 2*3.5=7, but 3.5 isn't an integer.

┌──┬──┬──┬─┐
│●●│●●│●●│●│ 7 can't be grouped as groups of 2 (last group only has 1)
└──┴──┴──┴─┘

⚠️NOTE️️️⚠️

See divisible section.

Divisible

↩PREREQUISITES↩

Imagine that you have the integer numbers d and n (use the letters as placeholders for some arbitrary integer numbers). d is divisible by n if d÷nd \div n has a remainder of 0.

For example, 8 is divisible by...

In all of the above cases, there is no remainder. 8 wouldn't be divisible by a number like 3 because there would be a remainder. 8/3=2R2.

┌───┬───┬──┐
│●●●│●●●│●●│ 8 can't be grouped as groups of 3 (last group only has 2)
└───┴───┴──┘

⚠️NOTE️️️⚠️

The phrases evenly divisible, evenly divides and divisible all mean the same thing.

The phrase evenly divides into is the same as divides into but that it doesn't have a remainder. 4 divides into 8 (4/8=2), but 6 doesn't divide into 8 (6/8=0.75).

⚠️NOTE️️️⚠️

Divisible and multiple refer to the same idea. Saying that 275 is a multiple of 5 (5?=2755\cdot?=275) is the same as saying 275 is divisible by 5 (275÷5=?275\div5=?).

Common divisibility tests are simple tests you can do on a number to see if its divisible. To see if a number is divisible by...

The common divisibility test algorithm written as code is as follows:

arithmetic_code/CommonDivisibilityTest.py (lines 10 to 69):

def common_divisibility_test(num: WholeNumber) -> Set[WholeNumber]:
    log_indent()
    try:
        ret: Set[WholeNumber] = set()
    
        last_digit: WholeNumber = WholeNumber.from_digit(num.digits[0])  # last digit is always at 0 idx
    
        log(f'Testing if {num} divisible by 2...')
        if last_digit == WholeNumber.from_int(0) \
                or last_digit == WholeNumber.from_int(2) \
                or last_digit == WholeNumber.from_int(4) \
                or last_digit == WholeNumber.from_int(6) \
                or last_digit == WholeNumber.from_int(8):
            log(f'Yes')
            ret.add(WholeNumber.from_int(2))
        else:
            log(f'No')
    
        log(f'Testing if {num}  divisible by 5...')
        if last_digit == WholeNumber.from_int(0) \
                or last_digit == WholeNumber.from_int(5):
            log(f'Yes');
            ret.add(WholeNumber.from_int(5))
        else:
            log(f'No');
    
        log(f'Testing if {num}  divisible by 10...')
        if last_digit == WholeNumber.from_int(0):
            log(f'Yes');
            ret.add(WholeNumber.from_int(10))
        else:
            log(f'No');
    
        log(f'Testing if {num} divisible by 3...')
        reduced_num: WholeNumber = num.copy()
        while True:
            digits = reduced_num.digits
            if len(digits) == 1:
                break
            reduced_num = sum([WholeNumber.from_int(d) for d in digits], WholeNumber.from_int(0))
    
        if reduced_num == WholeNumber.from_int(3) \
                or reduced_num == WholeNumber.from_int(6) \
                or reduced_num == WholeNumber.from_int(9):
            log(f'Yes')
            ret.add(WholeNumber.from_int(3))
        else:
            log(f'No')
    
        log(f'Testing if {num}  divisible by 6...')
        if WholeNumber.from_int(2) in ret and WholeNumber.from_int(3) in ret:
            log(f'Yes')
            ret.add(WholeNumber.from_int(6))
        else:
            log(f'NO')
    
        return ret
    finally:
        log_unindent()

For example, the common divisibility tests for 18...

Factor

↩PREREQUISITES↩

Let's say you have an integer number. The factors of that number are the integers you can multiply together to get that number...

my_number: int = ...
factor1: int = ...
factor2: int = ...
if (factor1 * factor2 == my_number):
    print(f'{factor1} and {factor2} are factors of {my_number})

For example, the factors of 32 are...

... 1, 2, 4, 8, 16, and 32.

⚠️NOTE️️️⚠️

Shouldn't negative integers also be a factor? e.g. 32=-1*-32. It turns out that for positive integers, negative factors aren't included? For negative integers, they are. Factoring negative integers is discussed further below in this section.

See https://math.stackexchange.com/a/404789

The factors for any number will always be between 1 and that number (inclusive). A naive algorithm for finding the factors of any number would be to have a nested loop exhaustively check integers to see which are factors...

arithmetic_code/Factor.py (lines 8 to 28):

@log_decorator
def factor_naive(num: WholeNumber) -> Set[WholeNumber]:
    log(f'Factoring {num}...')
    log_indent()

    factors: Set[WholeNumber] = set()
    for factor1 in WholeNumber.range(WholeNumber.from_int(1), num, end_inclusive=True):
        for factor2 in WholeNumber.range(WholeNumber.from_int(1), num, end_inclusive=True):
            log(f'Testing if {factor1} and {factor2} are factors...')
            if factor1 * factor2 == num:
                factors.add(factor1)
                factors.add(factor2)
                log(f'Yes')
            else:
                log(f'No')

    log_unindent()
    log(f'{factors}')

    return factors

We can take advantage of the fact that division is the inverse of multiplication to optimize the algorithm above. The code below loops over each possible factor once, using it to calculate what the other factor would be and then checking it to make sure it's valid...

arithmetic_code/Factor.py (lines 32 to 79):

@log_decorator
def factor_fast(num: WholeNumber) -> Set[WholeNumber]:
    log(f'Factoring {num}...')
    log_indent()

    factors: Set[WholeNumber] = set()
    for factor1 in WholeNumber.range(WholeNumber.from_int(1), num, end_inclusive=True):
        log(f'Test if {factor1} is a factor...')
        factor2, remainder = num / factor1
        if remainder == WholeNumber.from_int(0):
            factors.add(factor1)
            factors.add(factor2)
            log(f'Yes: ({factor1} and {factor2} are factors)')
        else:
            log(f'No')

    log_unindent()
    log(f'{factors}')

    return factors
#MARKDOWN_FAST


#MARKDOWN_FASTEST
@log_decorator
def factor_fastest(num: WholeNumber) -> Set[WholeNumber]:
    log(f'Factoring {num}...')
    log_indent()

    factors: Set[WholeNumber] = set()
    for factor1 in WholeNumber.range(WholeNumber.from_int(1), num, end_inclusive=True):
        log(f'Test if {factor1} is a factor...')
        factor2, remainder = num / factor1
        if remainder == WholeNumber.from_int(0):
            factors.add(factor1)
            factors.add(factor2)
            log(f'Yes: ({factor1} and {factor2} are factors)')
        else:
            log(f'No')

        if factor2 <= factor1:
            break

    log_unindent()
    log(f'{factors}')

    return factors

The optimized algorithm above can be even further optimized by making it skip over calculations that give back repeat factors. As factor1 increases, factor2 decreases. Once factor1 => factor2, each is basically walking into domains the other was just in (they're each going to walk over integers the other already walked over). There's no point in continuing any further because the factors calculated past that point will just be duplicates of those prior. For example, when calculating the factors of 32...

Any factors calculated past factor1 => factor2 will be duplicates of factors that were already walked over...

arithmetic_code/Factor.py (lines 56 to 79):

@log_decorator
def factor_fastest(num: WholeNumber) -> Set[WholeNumber]:
    log(f'Factoring {num}...')
    log_indent()

    factors: Set[WholeNumber] = set()
    for factor1 in WholeNumber.range(WholeNumber.from_int(1), num, end_inclusive=True):
        log(f'Test if {factor1} is a factor...')
        factor2, remainder = num / factor1
        if remainder == WholeNumber.from_int(0):
            factors.add(factor1)
            factors.add(factor2)
            log(f'Yes: ({factor1} and {factor2} are factors)')
        else:
            log(f'No')

        if factor2 <= factor1:
            break

    log_unindent()
    log(f'{factors}')

    return factors

There are 2 special cases when dealing with factors...

The first is that all numbers are a factor of 0 (e.g. 0*5=0, 0*9999=0).

The second is that if the number were a negative integer, the factors would include negative numbers as well. For example, the factors of -8 are...

... -8, -4, -2, -1, 1, 2, 4, 8.

Prime

↩PREREQUISITES↩

A counting number with only 2 factors is called a prime number. That is, if a counting number is only divisible by 1 and it itself, it's a prime number. Examples of prime numbers: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, and 47.

A counting number with more than 2 factors is called a composite number. Examples of composite numbers: 4, 6, 8, 9, 10, 12, 14, 15, 16, 18, and 20.

⚠️NOTE️️️⚠️

The number 1 is neither a prime number nor a composite number. 1's only factor is itself: 1*1=1. Prime numbers need 2 factors (1 and itself) and composite numbers need more than 2 factors.

The algorithm to identify primes vs composites is as follows...

arithmetic_code/Factor.py (lines 83 to 100):

@log_decorator
def is_prime(num: WholeNumber) -> bool:
    log(f'Test if {num} is prime...')
    log_indent()

    num_factors = factor_fastest(num)

    # At a minimum, all counting numbers have the factors 1 and the number itself (2 factors). If
    # there are more factore than that, it's a composite. Otherwise, it's a primse.

    log_unindent()
    if len(num_factors) == 2:
        log(f'{num}\'s factors are {num_factors} -- it is a prime');
        return True
    else:
        log(f'{num}\'s factors are {num_factors} -- it is a composite');
        return False

Prime Factor

↩PREREQUISITES↩

Every composite number can be written as a product of prime numbers. For example...

The process of breaking down a composite number into a product of primes is called prime factorization. There are 2 algorithms that humans use to factorize primes: factor tree method and ladder method. Each method is described below.

Least Common Multiple

↩PREREQUISITES↩

The least common multiple is the process of taking 2 numbers and finding the smallest multiple between them. That is, if you listed out their multiples starting from 1, the first match between them would be the least common multiple.

There are 2 common algorithms used to find the least common multiple between 2 numbers.

The first algorithm is called the listing multiples method. It involves listing out the multiples for each number starting from 1 until there's a match. For example, finding the least common multiple between 4 and 6...

1 2 3 4 5 6 7 8 9
4 4 8 12 16 20 24 28 32 36
6 6 12 18 24 30 36

is 12 because 6*2=12 and 4*3=12.

The way to perform this algorithm as code is as follows...

arithmetic_code/LeastCommonMultiple.py (lines 12 to 41):

@log_decorator
def lcm_walk(num1: WholeNumber, num2: WholeNumber) -> Tuple[List[WholeNumber], List[WholeNumber]]:
    num1_multiples: List[WholeNumber] = []
    num2_multiples: List[WholeNumber] = []

    num1_counter = WholeNumber.from_int(1)
    num2_counter = WholeNumber.from_int(1)

    while True:
        log(f'Calculating {num1_counter} multiple of {num1}...')
        num1_multiple = num1 * num1_counter
        num1_multiples.append(num1_multiple)

        log(f'Calculating {num2_counter} multiple of {num2}...')
        num2_multiple = num2 * num2_counter
        num2_multiples.append(num2_multiple)

        log(f'Testing {num1_multiple} vs {num2_multiple}')
        if num1_multiple == num2_multiple:
            log(f'Matches! LCM is {num1_multiple}')
            break
        elif num1_multiple < num2_multiple:
            log(f'Increasing first multiple (multiple for {num1})')
            num1_counter += WholeNumber.from_int(1)
        elif num1_multiple > num2_multiple:
            log(f'Increasing second multiple (multiple for {num2})')
            num2_counter += WholeNumber.from_int(1)

    return num1_multiple

The second algorithm is called the prime factors method. It involves calculating the prime factors for each number and merging them to get the least common multiple. For example, finding the least common multiple between 4 and 6...

The way to perform this algorithm as code is as follows...

arithmetic_code/LeastCommonMultiple.py (lines 45 to 76):

@log_decorator
def lcm_prime_factorize(num1: WholeNumber, num2: WholeNumber) -> WholeNumber:
    log(f'Calculating prime factors for {num1}...')
    num1_primes = sorted(factor_tree(num1).get_prime_factors())
    log(f'{num1_primes}')

    log(f'Calculating prime factors for {num2}...')
    num2_primes = sorted(factor_tree(num2).get_prime_factors())
    log(f'{num2_primes}')

    distinct_primes: Set[WholeNumber] = set()
    [distinct_primes.add(p) for p in num1_primes]
    [distinct_primes.add(p) for p in num2_primes]

    log(f'Combining prime factors to get LCM...')
    least_common_multiple = WholeNumber.from_int(1)
    least_common_multiple_primes = Counter()
    for prime in sorted(list(distinct_primes)):
        num1_count = num1_primes.count(prime)
        num2_count = num2_primes.count(prime)
        if num1_count >= num2_count:
            for i in WholeNumber.range(WholeNumber.from_int(0), WholeNumber.from_int(num1_count)):
                least_common_multiple = least_common_multiple * prime
            least_common_multiple_primes[prime] += num1_count
        else:
            for i in WholeNumber.range(WholeNumber.from_int(0), WholeNumber.from_int(num2_count)):
                least_common_multiple = least_common_multiple * prime
            least_common_multiple_primes[prime] += num2_count
    log(f'LCM is {least_common_multiple}')

    return least_common_multiple

Greatest Common Divisor

↩PREREQUISITES↩

The greatest common divisor is the process of taking 2 numbers and finding the largest possible divisor between the two of them. That is, finding the greatest number that evenly divides both numbers.

⚠️NOTE️️️⚠️

This is also referred to as the highest common factor -- you're finding the largest factor that's common in both of them. Common factors between the numbers will evenly divide both numbers.

There are 3 common algorithms used to find the greatest common divisor between 2 numbers.

The first algorithm is to test divisions on incrementally larger numbers until you reach the smaller of the 2 numbers. The largest tested number that was evenly divisible is the greatest common divisor. For example, for the numbers 22 and 8...

The greatest common divisor is 2.

The way to perform this algorithm as code is as follows...

arithmetic_code/GreatestCommonDivisor.py (lines 9 to 33):

@log_decorator
def gcd_naive(num1: WholeNumber, num2: WholeNumber) -> WholeNumber:
    log(f'Calculating gcd for {num1} and {num2}...')
    log_indent()

    log(f'Sorting to determine smaller input...')
    min_num = min(num1, num2)

    log(f'Testing up to smaller input ({min_num})...')
    log_indent()
    for i in WholeNumber.range(WholeNumber.from_str('1'), min_num, True):
        log(f'Testing {i}...')
        quotient1, remainder1 = num1 / i
        quotient2, remainder2 = num2 / i
        if remainder1 == 0 and remainder2 == 0:
            log(f'{num1} and {num2} are both divisible by {i}...')
            found = i
        else:
            log(f'{num1} and {num2} are NOT both divisible by {i}...')
    log_unindent()

    log_unindent()
    log(f'GCD is {found}')
    return found

The second algorithm is to factor both numbers and take the largest common factor between them. The largest common factor is the greatest common divisor. For example, for the numbers 22 and 8, ...

The greatest common factor between them is 2.

⚠️NOTE️️️⚠️

You can also use prime factorization. Prime factorize both numbers to their prime factors -- any factors contained in both are prime factors of the greatest common divisor. For example...

Kroki diagram output

The way to perform this algorithm as code is as follows...

arithmetic_code/GreatestCommonDivisor.py (lines 37 to 58):

@log_decorator
def gcd_factor(num1: WholeNumber, num2: WholeNumber) -> WholeNumber:
    log(f'Calculating gcd for {num1} and {num2}...')
    log_indent()

    log(f'Calculating factors for {num1}...')
    factors1 = factor_fastest(num1)
    log(f'Factors for {num1}: {factors1}')

    log(f'Calculating factors for {num2}...')
    factors2 = factor_fastest(num2)
    log(f'Factors for {num2}: {factors2}')

    log(f'Finding common factors...')
    common_factors = factors1 & factors2  # set intersection
    log(f'Common factors for {num1} and {num2}: {common_factors}')

    found = max(common_factors)

    log_unindent()
    log(f'GCD is {found}')
    return found

The third algorithm is to use Euclid's algorithm to compute the greatest common divisor. This is the algorithm most used by both humans and computers to calculate the greatest common divisor because, for large numbers, it's less labour intensive than the other two methods.

Imagine the numbers 8 and 22. The algorithm starts by sorting the numbers from largest to smallest and dividing them:

It then takes the divisor and the remainder, sorts them from largest to smallest, and divides them again:

It keeps repeating this process until the remainder reaches 0. For this example, it only needs to repeat the process one more time:

The greatest common factor is the divisor when the remainder is 0. In this example, it's 2.

The way to perform this algorithm as code is as follows...

arithmetic_code/GreatestCommonDivisor.py (lines 63 to 85):

@log_decorator
def gcd_euclid(num1: WholeNumber, num2: WholeNumber) -> WholeNumber:
    log(f'Calculating gcd for {num1} and {num2}...')
    log_indent()

    next_nums = [num1, num2]

    while True:
        log(f'Sorting {next_nums}...')
        next_nums.sort()  # sort smallest to largest
        next_nums.reverse()  # reverse it so that it's largest to largest
        log(f'Checking if finished ({next_nums[1]} == 0?)...')
        if next_nums[1] == WholeNumber.from_int(0):
            found = next_nums[0]
            break

        log(f'Dividing {next_nums} and grabbing the remainder for the next test...')
        _, remainder = next_nums[0] / next_nums[1]
        next_nums = [next_nums[1], remainder]

    log_unindent()
    log(f'GCD is {found}')
    return found

⚠️NOTE️️️⚠️

The following is my attempt at explaining Euclid's algorithm after reading several online resources. You need an understanding of geometry and algebra before continuing.

Fraction Number

↩PREREQUISITES↩

Kroki diagram output

Fractions are a way of representing numbers with fractional parts. The syntax for a fraction is numeratordenominator\frac{numerator}{denominator}, where the...

For example, if 4 parts make up a whole (denominator) and you have 9 of those parts (numerator), that's represented as 94\frac{9}{4}.

Concept diagram for fraction 0 / 4

Kroki diagram output

You can think of fractions as unresolved integer division operations. That is, rather than performing the division, the division is left as-is and the entire thing is treated as a value. In the example above, performing 9÷49 \div 4 results in 2R1, which is exactly the same value as represented by the fraction 94\frac{9}{4}. As the circle diagram above shows, 2 wholes are available and 1 remaining part.

Since a fraction represent integer division, the same rules as integer division apply:

  1. Recall that with integer division, if the dividend and the divisor have different sign then the quotient comes out negative. The same division rules apply to fractions. For example, ...

  2. Recall that with division, the divisor (number being divided by) can't be 0. The same rule applies to fractions. For example, ...

If a fraction has ...

⚠️NOTE️️️⚠️

The term improper doesn't seem to mean anything bad? See http://mathforum.org/library/drmath/view/70437.html for reasoning as to why they're called proper vs improper.

⚠️NOTE️️️⚠️

I haven't seen it done a lot but the term quotient may be used to describe a fraction. Since a fraction is essentially an unresolved division operation, the fraction as a whole represents the quotient. As such, a fraction can be referred to as a quotient.

The term ratio may also be used to refer to a fraction.

Equivalent Fraction

Two fractions are called equivalent fractions if they represent the same value. That is, the number of pieces may be different, but the overall value represented by the fraction is the same. For example, 32\frac{3}{2}, 64\frac{6}{4}, and 128\frac{12}{8} are all considered equivalent fractions because they represent the same value:

Each fraction has different sized pieces, but the overall value covered by those pieces (the gray region) is the same.

Simplification

↩PREREQUISITES↩

Of all the equivalent fractions that represent a value, one of those fractions represents that value in the smallest number of pieces possible. This fraction is called the simplified fraction. For the example above, 32\frac{3}{2} is the simplified fraction for both 128\frac{12}{8} and 64\frac{6}{4}:

Algorithmically, a fraction is considered a simplified fraction if no common factors exist between its numerator and its denominator (other than 1). For example, for the fraction 128\frac{12}{8}, the...

If a fraction isn't simplified, dividing the numerator and denominator by the highest common factor will make it simplified. In the example above, the highest common factor is 4. As such, dividing both the numerator and denominator by 4 will give the simplified fraction 32\frac{3}{2}.

⚠️NOTE️️️⚠️

The process described above is getting the greatest common divisor / highest common factor for the 2 denominators, then dividing both denominators by it.

arithmetic_code/FractionNumber.py (lines 246 to 282):

@log_decorator
def simplify(self: FractionNumber) -> FractionNumber:
    # Sign is on the numerator
    log(f'Simplifying {self}...')
    log_indent()

    log(f'Calculating GCD for ({self._numerator.magnitude}) and ({self._denominator.magnitude})...')
    gcd = gcd_euclid(self._numerator.magnitude, self._denominator.magnitude)
    log(f'GCD is {gcd}')

    log(f'Dividing numerator ({self._numerator.magnitude}) by {gcd}...')
    new_num, _ = self._numerator.magnitude / gcd
    log(f'New numerator is {new_num}...')

    log(f'Dividing denominator ({self._denominator.magnitude}) by {gcd}...')
    new_den, _ = self._denominator.magnitude / gcd
    log(f'New numerator is {new_den}...')

    # Sign of fraction is on the numerator
    if self.sign == Sign.NEGATIVE:  # if original was negative, so will the simplified
        res = FractionNumber(
            IntegerNumber(Sign.NEGATIVE, new_num),
            IntegerNumber(Sign.POSITIVE, new_den))
    elif self.sign == Sign.POSITIVE:  # if original was positive, so will the simplified
        res = FractionNumber(
            IntegerNumber(Sign.POSITIVE, new_num),
            IntegerNumber(Sign.POSITIVE, new_den))
    else:  # if original was 0 (no sign), so will the simplified
        res = FractionNumber(
            IntegerNumber(None, new_num),
            IntegerNumber(Sign.POSITIVE, new_den))

    log_unindent()
    log(f'{self} simplified to: {res}')

    return res

Common Denominator

↩PREREQUISITES↩

Given a pair of fractions that have different denominators, you can find a pair of equivalent fractions that share a common denominator. For example, the fractions 12\frac{1}{2} and 13\frac{1}{3}...

... have the following equivalent fractions that share a common denominator...

For any 2 fractions, the easiest algorithm to find equivalent fractions with common denominators is to multiply the numerator and denominator of each fraction by the denominator of the other fraction. So in the example above, the ...

⚠️NOTE️️️⚠️

If you already know fraction multiplication, you're effectively doing fraction multiplication here...

arithmetic_code/FractionNumber.py (lines 96 to 124):

@staticmethod
@log_decorator
def common_denominator_naive(lhs: FractionNumber, rhs: FractionNumber) -> (FractionNumber, FractionNumber):
    # Sign is only kept on the numerator, not the denominator
    log(f'Getting {lhs} and {rhs} to common denominator equivalent fractions')
    if lhs._denominator != rhs._denominator:
        log_indent()

        log(f'Calculating common denominator...')
        common_denominator = rhs._denominator * lhs._denominator
        log(f'{common_denominator}')

        log(f'Calculating numerator for LHS ({lhs})...')
        lhs_numerator = lhs._numerator * rhs._denominator
        log(f'{lhs_numerator}')

        log(f'Calculating numerator for RHS ({rhs})...')
        rhs_numerator = rhs._numerator * lhs._denominator
        log(f'{rhs_numerator}')

        log_unindent()

        lhs_equiv = FractionNumber(lhs_numerator, common_denominator)
        rhs_equiv = FractionNumber(rhs_numerator, common_denominator)
        log(f'Result: {lhs} -> {lhs_equiv}, {rhs} -> {rhs_equiv}')
        return lhs_equiv, rhs_equiv
    else:
        log(f'Fractions already have a common denominator')
        return lhs, rhs

The problem with the algorithm above is that it can result in fractions that have large numerators and denominators. For example, using the algorithm above to get the common denominator for 415\frac{4}{15} and 510\frac{5}{10} results in 40150\frac{40}{150} and 75150\frac{75}{150}.

A better approach that often leads to smaller numerators and denominators is to first figure out what the least common multiple between the denominators is (least common denominator). By figuring out what the least common denominator is, you can then work backwards to find the equivalent fractions that have those denominators:

  1. Get the least common multiple of the denominators from both fractions.
  2. For the first fraction...
    1. Divide the least common multiple by the denominator.
    2. Multiply the numerator and denominator by the result of the previous step.
  3. For the second fraction...
    1. Divide the least common multiple by the denominator.
    2. Multiply the numerator and denominator by the result of the previous step.

So for the example above, the least common denominator for 15 and 10 is 30...

⚠️NOTE️️️⚠️

If you already know fraction multiplication, you're effectively doing fraction multiplication here...

arithmetic_code/FractionNumber.py (lines 128 to 159):

@staticmethod
@log_decorator
def common_denominator_lcm(lhs: FractionNumber, rhs: FractionNumber) -> (FractionNumber, FractionNumber):
    # Sign is only kept on the numerator, not the denominator
    log(f'Getting {lhs} and {rhs} to common denominator equivalent fractions')
    if lhs._denominator != rhs._denominator:
        log_indent()

        log(f'Calculating common denominator...')
        common_denominator = lcm_prime_factorize(rhs._denominator.magnitude, lhs._denominator.magnitude)
        common_denominator = IntegerNumber(Sign.POSITIVE, common_denominator)
        log(f'{common_denominator}')

        log(f'Calculating numerator for LHS ({lhs})...')
        multiple, _ = common_denominator / lhs._denominator
        lhs_numerator = lhs._numerator * multiple
        log(f'{lhs_numerator}')

        log(f'Calculating numerator for RHS ({rhs})...')
        multiple, _ = common_denominator / rhs._denominator
        rhs_numerator = rhs._numerator * multiple
        log(f'{rhs_numerator}')

        log_unindent()

        lhs_equiv = FractionNumber(lhs_numerator, common_denominator)
        rhs_equiv = FractionNumber(rhs_numerator, common_denominator)
        log(f'Result: {lhs} -> {lhs_equiv}, {rhs} -> {rhs_equiv}')
        return lhs_equiv, rhs_equiv
    else:
        log(f'Fractions already have a common denominator')
        return lhs, rhs

Equality

↩PREREQUISITES↩

Conceptually, you can think of fraction equality as comparing two fractions with similar sized parts to see if they have the same number of parts. That is, as long as the number of parts used to represent a whole (denominator) is the same between both fractions, testing to see if the fractions are equal is simply testing to see if the individual parts (numerators) are equal.

For example, the denominator for the fractions 14\frac{1}{4} and 24\frac{2}{4} is 4. Since the fractions have a common denominator, you can test if they're equal by applying integer equality to the numerators...

14=24\frac{1}{4} = \frac{2}{4} is computed as 1=21 = 2 (false).

If the fractions being compared don't have a common denominator, you'll need to find equivalent fractions that do. The best way to do this is to use the least common denominator method. For example, before being able to compare 12\frac{1}{2} and 23\frac{2}{3}, they need to be converted to equivalent fractions that share a common denominator...

36=46\frac{3}{6} = \frac{4}{6} is computed as 3=43 = 4 (false).

The way to perform this algorithm via code is as follows...

arithmetic_code/FractionNumber.py (lines 303 to 338):

@log_decorator
def __eq__(lhs: FractionNumber, rhs: FractionNumber) -> bool:
    log(f'Equality testing {lhs} and {rhs}...')
    log_indent()

    # Sign is only kept on the numerator, not the denominator
    log(f'Checking if denominators are the same...')
    if lhs._denominator != rhs._denominator:
        log(f'Not same -- finding equivalent fractions with common denominator...')
        log_indent()

        log(f'Calculating common denominator...')
        denominator = rhs._denominator * lhs._denominator
        log(f'{denominator}')

        log(f'Scaling numerator for {lhs} so denominator becomes {denominator}...')
        lhs_numerator = lhs._numerator * rhs._denominator
        log(f'Numerator: {lhs_numerator} Denominator: {denominator}')

        log(f'Scaling numerator for {rhs} so denominator becomes {denominator}...')
        rhs_numerator = rhs._numerator * lhs._denominator
        log(f'Numerator: {rhs_numerator} Denominator: {denominator}')

        log_unindent()
    else:
        log(f'Same')
        lhs_numerator = lhs._numerator
        rhs_numerator = rhs._numerator
        denominator = rhs._denominator

    log(f'Testing {lhs_numerator} == {rhs_numerator}...')
    ret = lhs_numerator == rhs_numerator
    log(f'{ret}')

    return ret

Less Than

↩PREREQUISITES↩

Conceptually, you can think of fraction less than as comparing two fractions with similar sized parts to see which has less parts. That is, as long as the number of parts used to represent a whole (denominator) is the same between both fractions, testing to see which fraction is less is simply testing to see which has less individual parts (numerators).

For example, the denominator for the fractions 14\frac{1}{4} and 24\frac{2}{4} is 4. Since the fractions have a common denominator, you can test to see which is less by applying integer less than to the numerators...

14<24\frac{1}{4} < \frac{2}{4} is computed as 1<21 < 2 (true).

If the fractions being compared don't have a common denominator, you'll need to find equivalent fractions that do. The best way to do this is to use the least common denominator method. For example, before being able to compare 14\frac{1}{4} and 16\frac{1}{6}, they need to be converted to equivalent fractions that share a common denominator...

312<212\frac{3}{12} < \frac{2}{12} is computed as 3<23 < 2 (false).

The way to perform this algorithm via code is as follows...

arithmetic_code/FractionNumber.py (lines 341 to 376):

@log_decorator
def __lt__(lhs: FractionNumber, rhs: FractionNumber) -> bool:
    log(f'Less than testing {lhs} and {rhs}...')
    log_indent()

    # Sign is only kept on the numerator, not the denominator
    log(f'Checking if denominators are the same...')
    if lhs._denominator != rhs._denominator:
        log(f'Not same -- finding equivalent fractions with common denominator...')
        log_indent()

        log(f'Calculating common denominator...')
        denominator = rhs._denominator * lhs._denominator
        log(f'{denominator}')

        log(f'Scaling numerator for {lhs} so denominator becomes {denominator}...')
        lhs_numerator = lhs._numerator * rhs._denominator
        log(f'Numerator: {lhs_numerator} Denominator: {denominator}')

        log(f'Scaling numerator for {rhs} so denominator becomes {denominator}...')
        rhs_numerator = rhs._numerator * lhs._denominator
        log(f'Numerator: {rhs_numerator} Denominator: {denominator}')

        log_unindent()
    else:
        log(f'Same')
        lhs_numerator = lhs._numerator
        rhs_numerator = rhs._numerator
        denominator = rhs._denominator

    log(f'Testing {lhs_numerator} < {rhs_numerator}...')
    ret = lhs_numerator < rhs_numerator
    log(f'{ret}')

    return ret

Greater Than

↩PREREQUISITES↩

Conceptually, you can think of fraction greater than as comparing two fractions with similar sized parts to see which has more parts. That is, as long as the number of parts used to represent a whole (denominator) is the same between both fractions, testing to see which fraction is more is simply testing to see which has more individual parts (numerators).

For example, the denominator for the fractions 14\frac{1}{4} and 24\frac{2}{4} is 4. Since the fractions have a common denominator, you can test to see which is more by applying integer less than to the numerators...

14>24\frac{1}{4} > \frac{2}{4} is computed as 1>21 > 2 (false).

If the fractions being compared don't have a common denominator, you'll need to find equivalent fractions that do. The best way to do this is to use the least common denominator method. For example, before being able to compare 14\frac{1}{4} and 16\frac{1}{6}, they need to be converted to equivalent fractions that share a common denominator...

312>212\frac{3}{12} > \frac{2}{12} is computed as 3>23 > 2 (true).

The way to perform this algorithm via code is as follows...

arithmetic_code/FractionNumber.py (lines 382 to 417):

@log_decorator
def __gt__(lhs: FractionNumber, rhs: FractionNumber) -> bool:
    log(f'Greater than testing {lhs} and {rhs}...')
    log_indent()

    # Sign is only kept on the numerator, not the denominator
    log(f'Checking if denominators are the same...')
    if lhs._denominator != rhs._denominator:
        log(f'Not same -- finding equivalent fractions with common denominator...')
        log_indent()

        log(f'Calculating common denominator...')
        denominator = rhs._denominator * lhs._denominator
        log(f'{denominator}')

        log(f'Scaling numerator for {lhs} so denominator becomes {denominator}...')
        lhs_numerator = lhs._numerator * rhs._denominator
        log(f'Numerator: {lhs_numerator} Denominator: {denominator}')

        log(f'Scaling numerator for {rhs} so denominator becomes {denominator}...')
        rhs_numerator = rhs._numerator * lhs._denominator
        log(f'Numerator: {rhs_numerator} Denominator: {denominator}')

        log_unindent()
    else:
        log(f'Same')
        lhs_numerator = lhs._numerator
        rhs_numerator = rhs._numerator
        denominator = rhs._denominator

    log(f'Testing {lhs_numerator} > {rhs_numerator}...')
    ret = lhs_numerator > rhs_numerator
    log(f'{ret}')

    return ret

Addition

↩PREREQUISITES↩

Conceptually, you can think of fraction addition as adding together parts. That is, as long as the number of parts used to represent a whole (denominator) is the same between both fractions, adding them together is simply adding together the individual parts (numerators).

For example, the denominator for the fractions 14\frac{1}{4} and 24\frac{2}{4} is 4. Since the fractions have a common denominator, you can add them together by adding the numerators while keeping the denominator...

Treat the sign of the fraction as if it were on the numerator. For example, adding 14- \frac{1}{4} and 24\frac{2}{4} results in 14- \frac{1}{4} -- 1+2-1 + 2 results in 1-1, so the resulting fraction is 14\frac{-1}{4}.

If the fraction being added don't have a common denominator, you'll need to find equivalent fractions that do. The best way to do this is to use the least common denominator method. For example, before being able to add 14\frac{1}{4} and 16\frac{1}{6}, they need to be converted to equivalent fractions that share a common denominator...

arithmetic_code/FractionNumber.py (lines 163 to 179):

@log_decorator
def __add__(lhs: FractionNumber, rhs: FractionNumber) -> FractionNumber:
    # Sign is only kept on the numerator, not the denominator
    log(f'Adding {lhs} and {rhs}...')
    log_indent()

    log(f'Converting {lhs} and {rhs} to equivalent fractions with least common denominator...')
    lhs, rhs = FractionNumber.common_denominator_lcm(lhs, rhs)
    log(f'Equivalent fractions: {lhs} and {rhs}')
    log(f'Adding numerators of {lhs} and {rhs}...')
    res = FractionNumber(lhs._numerator + rhs._numerator, lhs._denominator)

    log_unindent()
    log(f'Result: {res}')

    return res

Subtraction

↩PREREQUISITES↩

Conceptually, you can think of fraction subtraction as subtracting parts. That is, as long as the number of parts used to represent a whole (denominator) is the same between both fractions, subtracting them is simply subtracting the individual parts (numerators).

For example, the denominator for the fractions 24\frac{2}{4} and 14\frac{1}{4} is 4. Since the fractions have a common denominator, you can subtract them by subtracting the numerators while keeping the denominator...

Treat the sign of the fraction as if it were on the numerator. For example, subtracting 14- \frac{1}{4} and 24\frac{2}{4} results in 34- \frac{3}{4} -- 12-1 - 2 results in 3-3, so the resulting fraction is 34\frac{-3}{4}.

If the fraction being subtracted don't have a common denominator, you'll need to find equivalent fractions that do. The best way to do this is to use the least common denominator method. For example, before being able to subtract 14\frac{1}{4} and 16\frac{1}{6}, they need to be converted to equivalent fractions that share a common denominator...

arithmetic_code/FractionNumber.py (lines 182 to 198):

@log_decorator
def __sub__(lhs: FractionNumber, rhs: FractionNumber) -> FractionNumber:
    # Sign is only kept on the numerator, not the denominator
    log(f'Subtracting {lhs} and {rhs}...')
    log(f'Converting {lhs} and {rhs} to equivalent fractions with least common denominator...')

    log(f'Converting {lhs} and {rhs} to equivalent fractions with least common denominator...')
    lhs, rhs = FractionNumber.common_denominator_lcm(lhs, rhs)
    log(f'Equivalent fractions: {lhs} and {rhs}')
    log(f'Subtracting numerators of {lhs} and {rhs}...')
    res = FractionNumber(lhs._numerator - rhs._numerator, lhs._denominator)

    log_unindent()
    log(f'Result: {res}')

    return res

Multiplication

↩PREREQUISITES↩

Conceptually, you can think of fraction multiplication as an extension to integer multiplication. In integer multiplication, you're repeatedly adding the same value for a certain number of iterations. For example, in 424 \cdot 2, the number 4 is being added for 2 iterations: 4+44 + 4.

Fraction multiplication follows the same concept but may also involve the adding of a fractional value. For example, imagine 4524 \cdot \frac{5}{2}. Recall that fractions can be thought of as unresolved integer division -- the fraction 52\frac{5}{2} is just another way of saying 5÷25 \div 2.

If you perform 5÷25 \div 2, the quotient would be 2R12R1...

Concept diagram for fraction 0 / 2

As such, 4524 \cdot \frac{5}{2} is just another way of saying 4 should be added for 2 and a half iterations: 4+4+24 + 4 + 2.

⚠️NOTE️️️⚠️

2 is half of 4. That's why there's a 2 as the last addition.

The human understandable algorithm for fraction multiplication relies on two ideas...

  1. Any fraction can be broken down as repetitive fraction addition of a single piece. For example, the fraction 46\frac{4}{6} can be written as 16+16+16+16\frac{1}{6} + \frac{1}{6} + \frac{1}{6} + \frac{1}{6}.

    Since multiplication is repetitive addition, the above addition can be written as 4164 \cdot \frac{1}{6}.

  2. If you have two fractions that are both single pieces (both have 1 as their numerator), the algorithm for multiplying them together is to keep the 1 in the numerator spot but multiply the denominators together. For example, 1213\frac{1}{2} \cdot \frac{1}{3} is 16\frac{1}{6}.

    To understand why this works, visualize the fractions as the slicing of a whole:

    Start with a whole...

    Concept diagram for fraction 0 / 1

    Take 12\frac{1}{2} of that whole...

    Concept diagram for fraction 0 / 2

    Take 13\frac{1}{3} of that 12\frac{1}{2}...

    Concept diagram for fraction 0 / 6

    The result is 1 of 6 parts: 16\frac{1}{6}, exactly the same as what you would get if you were to keep the 1 in the numerator spot but multiply the denominators together (the algorithm).

Any two fractions can be multiplied together by...

  1. breaking each fraction into the multiplication of a single piece (idea 1 above).
  2. multiplying the integers together.
  3. multiplying the single piece fractions together (idea 2 above).
  4. multiplying the result of step 2 with the result of step 3 (idea 1 above).

Idea 1 applies to step 4 because the result of step 2 will always be a single piece and the result of step 3 will always be an integer.

For example, to perform 2334\frac{2}{3} \cdot \frac{3}{4}, begin by breaking each fraction (idea 1): 2133142 \cdot \frac{1}{3} \cdot 3 \cdot \frac{1}{4}.

Then, multiply the integers together: 13146\frac{1}{3} \cdot \frac{1}{4} \cdot 6

⚠️NOTE️️️⚠️

This is possible because multiplication is commutative -- numbers can be multiplied together in any order and the result will always be the same.

Then, multiply the single piece fractions together (idea 2): 1126\frac{1}{12} \cdot 6

⚠️NOTE️️️⚠️

This is possible because multiplication is commutative -- numbers can be multiplied together in any order and the result will always be the same.

Finally, multiply the single piece fraction with the integer (idea 1): 612\frac{6}{12}

If you look closely at the example above, you may notice that the final product is the product of the numerators and the product of the denominators. For example, in 2334\frac{2}{3} \cdot \frac{3}{4}, the ...

... resulting in the final product 612\frac{6}{12}.

This is the accepted algorithm for multiplying any 2 fractions together. The product of fractions is the product of their numerators over the product of their denominators.

arithmetic_code/FractionNumber.py (lines 201 to 219):

@log_decorator
def __mul__(lhs: FractionNumber, rhs: FractionNumber) -> FractionNumber:
    # Sign is only kept on the numerator, not the denominator
    log(f'Multiplying {lhs} and {rhs}')
    log_indent()

    log(f'Multiplying numerators {lhs._numerator} and {rhs._numerator}...')
    numerator = lhs._numerator * rhs._numerator

    log(f'Multiplying denominators {lhs._denominator} and {rhs._denominator}...')
    denominator = lhs._denominator * rhs._denominator

    res = FractionNumber(numerator, denominator)

    log_unindent()
    log(f'Result: {res}')

    return res

⚠️NOTE️️️⚠️

If you understand algebra, the reasoning for why the above algorithm works is available at http://mathforum.org/library/drmath/view/63841.html. It uses the same concept of breaking down fractions into single pieces.

Reciprocal

↩PREREQUISITES↩

The reciprocal of a fraction is when you take that fraction and flip its numerator and denominator. For example, the reciprocal of 56-\frac{5}{6} is 65-\frac{6}{5}.

When you multiply a fraction by its reciprocal, you will always end up with a whole. For example, 2772\frac{2}{7} \cdot \frac{7}{2} is 1414\frac{14}{14}.

arithmetic_code/FractionNumber.py (lines 234 to 243):

@log_decorator
def reciprocal(self: FractionNumber) -> FractionNumber:
    # Sign is on the numerator
    log(f'Getting reciprocal of {self}')

    res = FractionNumber(self._denominator, self._numerator)
    log(f'Result: {res}')

    return res

Mixed Number

↩PREREQUISITES↩

Any fraction can be written out as a mixed number, where the wholes are written as a normal integer and the remaining portion is written as a fraction. Recall that fractions can be thought of as unresolved integer division. For example, the fraction 154\frac{15}{4} is equivalent to the division 15÷415 \div 4.

If you were to perform 15÷415 \div 4, the quotient would be 3R33R3 -- 3 wholes with 3 remaining pieces...

Concept diagram for fraction 0 / 4

As such, 15÷415 \div 4 can be written as the mixed number 3343 \frac{3}{4}.

⚠️NOTE️️️⚠️

Don't get confused -- the mixed number 3343 \frac{3}{4} means 3+343 + \frac{3}{4}, it does not mean 3343 \cdot \frac{3}{4} (multiplication).

To convert a...

Division

↩PREREQUISITES↩

Conceptually, you can think of fraction division as an extension to integer division. In integer division, you're repeatedly subtracting the some value until it reaches 0. For example, in 8÷28 \div 2, the number 8 is subtracted for 4 iterations to reach 0: 822228 - 2 - 2 - 2 - 2 is 0.

Fraction division follows the same concept but may also involve the subtraction of a fractional value. For example, imagine 8÷328 \div \frac{3}{2}. You can successfully subtract 32\frac{3}{2} for 5 iterations before the value becomes smaller than 32\frac{3}{2} but larger than 0...

832323232328 - \frac{3}{2} - \frac{3}{2} - \frac{3}{2} - \frac{3}{2} - \frac{3}{2}