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.
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.
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")
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.
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