Meta Project

The Unofficial Meta Documentation

BIG Numbers with Meta

Why BIG Numbers

Seriously? Because people need them!

This is the naive way of implementing BIG numbers. Just using strings to represent numbers. Calculating with them as we all learned in elementary school.

It is hopelessly inefficient to calculate like this on the computer. And even if I follow the steps like learned in school, remember that all really simple calculations made in between, like "9" + "8" to add some digits within the numbers is done using conversions to binary format and adding like that.

The program

Well, let me present to you the awful code I came up with. You will notice a lot of code got duplicated. This is because I did not want to keep track of all called functions and return points using a stack. Methods will help in future to eliminate such bookkeeping.

Meta [
    File:    %bignumbers.meta
    Version: 1.0
    Date:    2-Jan-2025
    Purpose: {
        Perform ADDITION SUBTRACTION MULTIPLICATION en DIVISION on natural numbers larger
        than the NATURAL64! representation can handle.
    }
]

; Read input from a file so the program can be reused without recompiling each time
infile: to file! "./input-bignum.txt"

Either file-handle= try OPEN infile [
    write/line "Processing data.."
][
    write/line "Not able to open input file"
    bye
]

date: form now
year: copy cut find/last/tail date "-" 4
month: copy cut find/tail date "-" 3
day: copy cut date 1
day2: copy cut at date 2 1
date-time-size: 20
fillspace: ""
if "-" != day2 [
    day: join/with day day2
    decrement date-time-size
    fillspace: join/with " " fillspace
]
time: copy cut find/last/tail date "/" 8
if "+" = copy cut at time 8 1 [
    time: copy cut time 7
    decrement date-time-size
    fillspace: join/with " " fillspace
]
date: copy cut date date-time-size

out-file-name: join/with join/with join/with join/with
    join/with join/with join/with join/with
    "./output-bignum-"
    year "-" month "-" day "-" time
    ".txt"
outfile: to file! out-file-name

if not out-handle= try OPEN/NEW outfile [
    write/line "Not able to open output file"
    bye
]

; program-states
constant byte! [
GET-STATE= 1
GET-N1
GET-N2
GET-ON
]
state: GET-STATE

constant byte! [
NOOP= 0
BIG-ADDITION
BIG-SUBTRACTION
BIG-MULTIPLICATION
BIG-DIVISION
BIG-FACULTY
]

big-function: NOOP

help-text: {=== Meta BIG number (naive implementation) ===

This BIG number utility uses STRING! type to represent natural numbers.
This helps overcome the upper bound limitation of the NATURAL64! type numbers.

Supported operations are ADDITION, SUBTRACTION, MULTIPLICATION and DIVISION.

Input is done using an inputfile by the name input-bignum.txt in the current folder.

Commands should go on the first position of a line followed by the required inputs.

help        - prints this help message
stop        - halts the processing of the rest of the inputfile
add         - perform the addition of the two next input lines
subtract    - perform the subtraction  of the two next input lines, largest minus smallest
multiply    - perform the multiplication of the two next input lines
divide      - perform the division of the two next input lines, divides first by second

}
halted-text: {

 ------
Halted!}

add-text: {

Adding
}
and-text: {
to
}
gives-text: {
gives
}
sub-text: {

Calculate the difference between
}
sub2-text: {
and
}
mul-text: {

Multiplying
}
by-text: {
by
}
div-text: {

Dividing
}
div2-text: {
and remainder
}

report-lines: join/with join/with join/with {==============================================
 ==        BIG number output report        ===
 ==        } date fillspace {===
 =============================================
}
append out-handle report-lines

file-in-lines: ""

while not is-tail file-handle [
    inline: take/line file-handle
    input-line: ""
    forever [
        either 255 = count inline [
            input-line: join/with input-line inline
            inline: take/line file-handle
        ][
            input-line: join/with join/with input-line inline new-line
            break
        ]
    ]
    ; Here a line is read
    file-in-lines: join/with file-in-lines input-line
    ; There are no methods in Meta so each functionality is translated individually
    if "help" = copy cut input-line 4 [append out-handle help-text continue]
    if "stop" = copy cut input-line 4 [append out-handle halted-text break]
    if "add"  = copy cut input-line 3 [big-function: BIG-ADDITION state: GET-N1 continue]
    if "multiply" = copy cut input-line 8 [big-function: BIG-MULTIPLICATION state: GET-N1 continue]
    if "divide" = copy cut input-line 6  [big-function: BIG-DIVISION state: GET-N1 continue]
    if "subtract" = copy cut input-line 8  [big-function: BIG-SUBTRACTION state: GET-N1 continue]
    if state = GET-N2 [
        n2: copy cut input-line (count input-line) - 1
        state: GET-ON
    ]
    if state = GET-N1 [
        n1: copy cut input-line (count input-line) - 1
        either big-function = BIG-FACULTY [
            state: GET-ON
        ][
            state: GET-N2
        ]
    ]
    if state = GET-ON [
        if big-function = BIG-ADDITION [
            append out-handle add-text
            | append n1
            | append and-text
            | append n2
            | append gives-text
            carry: 0
            result: ""
            l1: count n1
            l2: count n2
            if l1 < l2 [n: n1 n1: n2 n2: n l: l1 l1: l2 l2: l]
            n1: at-last n1
            n2: at-last n2
            while l2 [
                plus: ((to byte! copy cut n1 1) + (to byte! copy cut n2 1) + carry)
                either plus <= 9 [
                    carry: 0
                    result: join/with to string! plus result
                ][
                    carry: 1
                    result: join/with copy cut skip to string! plus 1 1 result
                ]
                retreat n1
                retreat n2
                decrement l1
                decrement l2
            ]
            while l1 [
                plus: (to byte! copy cut n1 1) + carry
                either plus <= 9 [
                    carry: 0
                    result: join/with to string! plus result
                ][
                    carry: 1
                    result: join/with copy cut skip to string! plus 1 1 result
                ]
                retreat n1
                decrement l1
            ]
            if carry = 1 [
                result: join/with "1" result
            ]
            append out-handle result
            state: GET-STATE
            big-function: NOOP
        ]
        if big-function = BIG-SUBTRACTION [
            append out-handle sub-text
            | append n1
            | append sub2-text
            | append n2
            | append gives-text
            ; First get the largest / smallest
            l1: count n1
            l2: count n2
            result-trivial?: false
            either l1 != l2 [
                if l1 < l2 [n: n1 n1: n2 n2: n l: l1 l1: l2 l2: l]
            ][
                either n1 = n2 [
                    result: 0
                    result-trivial?: true
                ][
                    for index [1 (l1 - 1)] [
                        either (copy cut at n1 index 1) = (copy cut at n2 index 1) [
                            continue
                        ][
                            if (to byte! copy cut at n1 index 1) < (to byte! copy cut at n2 index 1) [
                                n: n1 n1: n2 n2: n l: l1 l1: l2 l2: l
                            ]
                            break
                        ]
                    ]
                ]
            ]
            ; n1 is now the largest
            n1: at-last n1
            n2: at-last n2
            memory: 0
            result: ""
            unless result-trivial? [
                while l2 [
                    minus: ((to byte! copy cut n1 1) - memory) + (10 - to byte! copy cut n2 1)
                    either minus <= 9 [
                        memory: 1
                        result: join/with to string! minus result
                    ][
                        memory: 0
                        result: join/with to string! remainder minus 10 result
                    ]
                    retreat n1
                    retreat n2
                    decrement l1
                    decrement l2
                ]
                while l1 [
                    minus: (to byte! copy cut n1 1) + (10 - memory)
                    either minus <= 9 [
                        memory: 1
                        result: join/with to string! minus result
                    ][
                        memory: 0
                        result: join/with to string! remainder minus 10 result
                    ]
                    retreat n1
                    decrement l1
                ]
            ]
            ; trim leading zeroes
            leading-zeroes: 0
            length-result: count result
            while leading-zeroes < length-result [
                if "0" = copy cut skip result leading-zeroes 1 [
                    increment leading-zeroes
                    continue
                ]
                break
            ]
            if leading-zeroes > 0 [
                result: skip result leading-zeroes
            ]
            append out-handle result
            state: GET-STATE
            big-function: NOOP
        ]
        if big-function = BIG-MULTIPLICATION [
            ; First get the biggest / smallest in LENGTH only
            append out-handle mul-text
            | append n1
            | append by-text
            | append n2
            | append gives-text
            l1: count n1
            l2: count n2
            if l1 != l2 [
                if l1 > l2 [n: n1 n1: n2 n2: n l: l1 l1: l2 l2: l]
            ]
            ; n1 is now the shortest
            n1: at-last n1
            ; start on 0
            multiplied: "0"
            mn2: n2
            while l1 [
                ; nu big-add met multiplied en (m)n2
                repcount: to byte! copy cut n1 1
                repeat repcount [
; ==== Start big add in multiply
                    carry: 0
                    result: ""
                    ml1: count multiplied
                    ml2: count mn2
                    multiplied: at-last multiplied
                    mn2: at-last mn2
                    while all [ml2 > 0 ml1 > 0][
                        plus: ((to byte! copy cut multiplied 1) + (to byte! copy cut mn2 1) + carry)
                        either plus <= 9 [
                            carry: 0
                            result: join/with to string! plus result
                        ][
                            carry: 1
                            result: join/with copy cut skip to string! plus 1 1 result
                        ]
                        retreat multiplied
                        retreat mn2
                        decrement ml1
                        decrement ml2
                    ]
                    either ml2 = 0 [
                        advance mn2
                        while ml1 [
                            plus: (to byte! copy cut multiplied 1) + carry
                            either plus <= 9 [
                                carry: 0
                                result: join/with to string! plus result
                            ][
                                carry: 1
                                result: join/with copy cut skip to string! plus 1 1 result
                            ]
                            retreat multiplied
                            decrement ml1
                        ]
                        ;advance multiplied ; not needed for it will be overwritten
                    ][
                        advance multiplied
                        while ml2 [
                            plus: (to byte! copy cut mn2 1) + carry
                            either plus <= 9 [
                                carry: 0
                                result: join/with to string! plus result
                            ][
                                carry: 1
                                result: join/with copy cut skip to string! plus 1 1 result
                            ]
                            retreat mn2
                            decrement ml2
                        ]
                        advance mn2
                    ]

                    if carry = 1 [
                        result: join/with "1" result
                    ]
; ==== End big add in multiply

                    multiplied: result
                ]
                mn2: join/with mn2 "0" ; ten hundred thousand ...
                retreat n1
                decrement l1
            ]
            append out-handle multiplied
            state: GET-STATE
            big-function: NOOP
        ]
        if big-function = BIG-DIVISION [
            append out-handle div-text
            | append n1
            | append by-text
            | append n2
            | append gives-text
            ; First get the largest / smallest
            l1: count n1
            l2: count n2
            save-n2: n2
            save-l2: l2
            result-trivial?: false
            either l1 != l2 [
                if l1 < l2 [
                    result: "0"
                    rest: n1
                    result-trivial?: true
                ]
            ][
                either n1 = n2 [
                    result: "1"
                    rest: "0"
                    result-trivial?: true
                ][
                    for index [1 (l1 - 1)] [
                        either (copy cut at n1 index 1) = (copy cut at n2 index 1) [
                            continue
                        ][
                            if (to byte! copy cut at n1 index 1) < (to byte! copy cut at n2 index 1) [
                                result: "0"
                                rest: n1
                                result-trivial?: true
                            ]
                            break
                        ]
                    ]
                ]
            ]
            unless result-trivial? [
                result: "0"
                n1-greater-than-n2?: true
                while n1-greater-than-n2? [
                ;    n1: SUBTRACTION n1 n2
                    memory: 0
                    wresult: ""
                    n1: at-last n1
                    n2: at-last n2
                    while l2 [
                        minus: ((to byte! copy cut n1 1) - memory) + (10 - to byte! copy cut n2 1)
                        either minus <= 9 [
                            memory: 1
                            wresult: join/with to string! minus wresult
                        ][
                            memory: 0
                            wresult: join/with to string! remainder minus 10 wresult
                        ]
                        retreat n1
                        retreat n2
                        decrement l1
                        decrement l2
                    ]
                    advance n2 ; will this fix it?
                    while l1 [
                        minus: (to byte! copy cut n1 1) + (10 - memory)
                        either minus <= 9 [
                            memory: 1
                            wresult: join/with to string! minus wresult
                        ][
                            memory: 0
                            wresult: join/with to string! remainder minus 10 wresult
                        ]
                        retreat n1
                        decrement l1
                    ]
                    if memory = 1 [wresult: join/with "1" wresult]
                    ; trim leading zeroes
                    leading-zeroes: 0
                    length-result: count wresult
                    while leading-zeroes < length-result [
                        if "0" = copy cut skip wresult leading-zeroes 1 [
                            increment leading-zeroes
                            continue
                        ]
                        break
                    ]
                    if leading-zeroes > 0 [
                        either leading-zeroes = length-result [
                            wresult: "0"
                        ][
                            wresult: skip wresult leading-zeroes
                        ]
                    ]
                    n1: wresult

                    ; INCREMENT RESULT COUNTER
                    dresult: ""
                    carry: 0
                    l1: count result
                    l2: 1
                    d1: result
                    d1: at-last d1

                    plus: ((to byte! copy cut d1 1) + 1 + carry)
                    either plus <= 9 [
                        carry: 0
                        dresult: join/with to string! plus dresult
                    ][
                        carry: 1
                        dresult: join/with copy cut skip to string! plus 1 1 dresult
                    ]
                    retreat d1
                    decrement l1
                    while l1 [
                        plus: (to byte! copy cut d1 1) + carry
                        either plus <= 9 [
                            carry: 0
                            dresult: join/with to string! plus dresult
                        ][
                            carry: 1
                            dresult: join/with copy cut skip to string! plus 1 1 dresult
                        ]
                        retreat d1
                        decrement l1
                    ]
                    if carry = 1 [
                        dresult: join/with "1" dresult
                    ]
                    ;n1: dresult
                    result: dresult
                    ; Is still n1-greater-than-n2?
                    l1: count n1
                    l2: save-l2
                    either l1 != l2 [
                        if l1 < l2 [
                            n1-greater-than-n2?: false
                        ]
                    ][
                        either n1 = n2 [
                            n1-greater-than-n2?: false
                        ][
                            for index [1 (l1 - 1)] [
                                either (copy cut at n1 index 1) = (copy cut at n2 index 1) [
                                    continue
                                ][
                                    if (to byte! copy cut at n1 index 1) < (to byte! copy cut at n2 index 1) [
                                        n1-greater-than-n2?: false
                                    ]
                                    break
                                ]
                            ]
                        ]
                    ]
                ]
                rest: n1
                if n1 = n2 [
                    ; INCREMENT RESULT COUNTER
                    dresult: ""
                    carry: 0
                    l1: count result
                    l2: 1
                    d1: result
                    d1: at-last d1
                    plus: ((to byte! copy cut d1 1) + 1 + carry)
                    either plus <= 9 [
                        carry: 0
                        dresult: join/with to string! plus dresult
                    ][
                        carry: 1
                        dresult: join/with copy cut skip to string! plus 1 1 dresult
                    ]
                    retreat d1
                    decrement l1
                    while l1 [
                        plus: (to byte! copy cut d1 1) + carry
                        either plus <= 9 [
                            carry: 0
                            dresult: join/with to string! plus dresult
                        ][
                            carry: 1
                            dresult: join/with copy cut skip to string! plus 1 1 dresult
                        ]
                        retreat d1
                        decrement l1
                    ]
                    if carry = 1 [
                        dresult: join/with "1" dresult
                    ]
                    result: dresult
                    rest: "0"
                ]
            ]
            append out-handle result
            | append div2-text
            | append rest
            state: GET-STATE
            big-function: NOOP
        ]
    ]
]

close file-handle
close out-handle

So we got BIG numbers in Meta, but yes this is the naive variant.

Multiplication improvement

It is very naive. Multiplication can be made MUCH more efficient.

If you think about it for every digit in the second operand, you need to add its digit value of times the first operand to the total, where you need to multiply that by ten to the power of the position, which is only adding a zero at the end.

So we only have to multiply the first operand by 2 to 9 to compute the values we need to add to the total very fast.

We can save these in separate strings. I show this.

n1: "123456"
; 0 x n1 = "0" we already knew this
; 1 x n1 = n1  and this too

; 2 x n1 = ( don't use Python to do this ;-) )
;          "246912"
; 3 x n1 = "370368"
; 4 x n1 = "493824"
; ...
; 9 x n1 = "1111104"

Saving these strings in n1-2 to n1-9, and we know how to calculate them: n1-9 = n1-8 + n1, n1-8 = n1-7 + n1, .. n1-2 = n1 + n1, that will improve performance.

n1: "123456"
n2: "987"

; n1 * n2 is

; "0" + n1-7 + (join/with n1-8 "0") + (join/with n1-9 "00")

Divide

When dividing we just subtract the second operand from the first. Like with multiplication, that is ridiculously inefficient.

When the first operand is more than 1 longer than the second, we know that we could at least subtract a multiple by a power of ten from the first. We can use this to subtract many multiples in a single calculation.

How to go on?

Despite these improvements we still need a proper BIG number thing worked out.

There are some rather good tiny C versions of BIGNUM libraries out there that could serve as example