BIGNUM v 2.5

[Agamemnus]

Um, I wanted to see if I could make something faster than Neo's BIGINT. So I tried and finally the result is BIGNUM. Right now it is just addition and multiplication, though.

I don't know if it is a good idea to continue, though. Seems to me like the best way to do this is to have an integer array, though. Maybe next version..

I'ma gonna post the code here 'cuz it saves me a lot of time n' trouble. Hope you don't mind the amount of initial comments. Standard on all my released programs..
'BigNum
'Release version 2.5
'© 2003 Agamemnus (Michael Romanovsky) -- warlordagamemnus@aol.com
'Member of Flyingsoft Programming Group -- http://www.geocities.com/pisforpi/flyingsoft/

'---------------------
'Purpose
'---------------------
'
'Fast multiplication/addition using strings..
'
'---------------------
'Last Updated
'---------------------
'May 17, 2003
'
'---------------------
'Disclaimer
'---------------------
'This program uses pure QBasic code and will not disrupt your computer
'in any way. If by any chance your computer IS disrupted, the creator
'is not liable for any damage to your computer. Why? Because by using
'this package you agree to be legally binded to this disclaimer. (and
'the Terms of Use) Have a nice day.
'
'---------------------
'Terms of Use
'---------------------
'
'If you use this for personal use, the following can be ignored.
'
'You may use any parts of this package without the author's permission
'provided that you
'1) Site the author's name in credits.
'2) Are using this for FREEWARE.
'
'If you are using this for non-commercial use, you may freely use this
'package, in whole or in part. Otherwise you must purchase a license to
'use this package however you deem fit, while still giving credit to the
'author. You may only obtain this license through written permission of
'author and the conditions for said license. You may initially contact
'the author through his email: warlordagamemnus@aol.com.

'$DYNAMIC
DECLARE SUB bit.draw (string1$, x1%, y1%)
DECLARE FUNCTION binary.convert$ (string1b$)
DECLARE FUNCTION multiply$ (string1m$, string2m$)
DECLARE FUNCTION add$ (string1$, string2$)
DECLARE SUB factorial (n%)
DECLARE SUB add2a ()
DECLARE SUB multiply2a ()

CLEAR

DIM SHARED number1(1 TO 1) AS INTEGER, number2(1 TO 1) AS INTEGER, len.number1%, len.number2%
DIM SHARED number1m(1 TO 1) AS INTEGER, number2m(1 TO 1) AS INTEGER, len.number1m%, len.number2m%
DIM SHARED number1f(1 TO 1) AS INTEGER, number2f(1 TO 1) AS INTEGER, len.number1f%, len.number2f%
DIM SHARED number1b&(1 TO 1), number2b%(1 TO 1)

SCREEN 9
CLS

test1% = 0
test2% = 1
test3% = 0
test4% = 0

IF test1% = 1 THEN
string1$ = ""
string2$ = ""
FOR I% = 1 TO 6000
string1$ = string1$ + LTRIM$(STR$(INT(RND * 10)))
string2$ = string2$ + LTRIM$(STR$(INT(RND * 10)))
NEXT I%
t1# = TIMER
a$ = add$(string1$, string2$)
t2# = TIMER - t1#
PRINT t2#
END IF

IF test2% = 1 THEN
t1# = TIMER
factorial (100)
t2# = TIMER - t1#
'PRINT t2#
END IF

IF test3% = 1 THEN
REDIM number1(1 TO 24001) AS INTEGER
REDIM number2(1 TO 24001) AS INTEGER
len.number1% = 24001
len.number2% = 24001
FOR I% = 1 TO 24000
number1(I%) = INT(RND * 10000)
number2(I%) = INT(RND * 10000)
NEXT I%

t1# = TIMER
FOR I% = 1 TO 50
add2a
NEXT I%
t2# = TIMER - t1#
PRINT t2#
END IF

'PRINT multiply("300", "3")
'string1b$ = "6"
'string1b$ = "012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789"
'bit.draw binary.convert$(string1b$), 0, 50

REM $STATIC
FUNCTION add$ (string1$, string2$)
diff4% = 4 - LEN(string1$) MOD 4: IF diff4% <> 4 THEN string1$ = STRING$(diff4%, "0") + string1$
diff4% = 4 - LEN(string2$) MOD 4: IF diff4% <> 4 THEN string2$ = STRING$(diff4%, "0") + string2$
len.number1% = LEN(string1$) / 4
len.number2% = LEN(string2$) / 4
IF len.number1% = len.number2% THEN
len.number1% = len.number1% + 1: len.number2% = len.number2% + 1
string1$ = "0000" + string1$: string2$ = "0000" + string2$
ELSE
IF len.number1% > len.number2% THEN
len.number1% = len.number1% + 1
string1$ = "0000" + string1$
ELSE
len.number2% = len.number2% + 1
string2$ = "0000" + string2$
END IF
END IF

REDIM number1(1 TO len.number1%) AS INTEGER
REDIM number2(1 TO len.number2%) AS INTEGER
j% = len.number1% * 4 - 3: FOR I% = 1 TO len.number1%
number1(I%) = VAL(MID$(string1$, j%, 4)): j% = j% - 4
NEXT I%
j% = len.number2% * 4 - 3: FOR I% = 1 TO len.number2%
number2(I%) = VAL(MID$(string2$, j%, 4)): j% = j% - 4
NEXT I%
add2a
IF len.number1% >= len.number2% THEN
FOR I% = 1 TO len.number1%
temp$ = LTRIM$(STR$(number1(I%)))
n% = 4 - LEN(temp$) MOD 4: IF n% <> 4 THEN temp$ = STRING$(n%, "0") + temp$
temp2$ = temp$ + temp2$
NEXT I%
ELSE
PRINT
FOR I% = 1 TO len.number2%
temp$ = LTRIM$(STR$(number2(I%)))
n% = 4 - LEN(temp$) MOD 4: IF n% <> 4 THEN temp$ = STRING$(n%, "0") + temp$
temp2$ = temp$ + temp2$
NEXT I%
END IF
DO
IF MID$(temp2$, 1, 1) <> "0" THEN EXIT DO
temp2$ = MID$(temp2$, 2, LEN(temp2$))
LOOP
REDIM number1(1 TO 1) AS INTEGER, number2(1 TO 1) AS INTEGER
add$ = temp2$
END FUNCTION

SUB add2a
IF len.number2% = len.number1% THEN
FOR I% = 1 TO len.number1%

IF carry% = 0 THEN
IF number2(I%) = 0 THEN GOTO ab2a
IF number1(I%) = 0 THEN number1(I%) = number2(I%): GOTO ab2a
temp& = number1(I%) + number2(I%)
ELSE
temp& = number1(I%) + number2(I%) + carry%
END IF
IF temp& > 9999 THEN temp2& = temp& MOD 10000: carry% = (temp& - temp2&) / 10000: number1(I%) = temp2&: GOTO ab2a
number1(I%) = temp&: carry% = 0
ab2a: NEXT I%
EXIT SUB
END IF

IF len.number2% > len.number1% THEN
diff2% = len.number2% - len.number1%
FOR I% = 1 TO len.number1%
IF carry% = 0 THEN
IF number1(I%) = 0 THEN GOTO ab2a2
j% = I% + diff2%
IF number2(j%) = 0 THEN number2(j%) = number1(I%): GOTO ab2a2
temp& = number2(j%) + number1(I%)
ELSE
temp& = number2(j%) + number1(I%) + carry%
END IF
IF temp& > 9999 THEN temp2& = temp& MOD 10000: carry% = (temp& - temp2&) / 10000: number2(j%) = temp2&: GOTO ab2a2
number2(j%) = temp&: carry% = 0
ab2a2: NEXT I%

IF carry% = 0 THEN EXIT SUB
j% = len.number1%
DO
j% = j% + 1
temp& = number2%(j%) + carry%
IF temp& > 9999 THEN
temp2& = temp& MOD 10000
carry% = (temp& - temp2&) / 10000
number2(j%) = temp2&
ELSE
number2(j%) = temp&
EXIT SUB
END IF
LOOP
EXIT SUB
END IF

diff2% = len.number1% - len.number2%
FOR I% = 1 TO len.number2%
IF carry% = 0 THEN
IF number2(I%) = 0 THEN GOTO ab2a3
j% = I% + diff2%
IF number1(j%) = 0 THEN number1(j%) = number2(I%): GOTO ab2a3
temp& = number1(j%) + number2(I%)
ELSE
temp& = number1(j%) + number2(I%) + carry%
END IF
IF temp& > 9999 THEN temp2& = temp& MOD 10000: carry% = (temp& - temp2&) / 10000: number1(j%) = temp2&: GOTO ab2a3
number1(j%) = temp&: carry% = 0
ab2a3: NEXT I%

IF carry% = 0 THEN EXIT SUB
j% = len.number2%
DO
j% = j% + 1
temp& = number1%(j%) + carry%
IF temp& > 9999 THEN
temp2& = temp& MOD 10000
carry% = (temp& - temp2&) / 10000
number1(j%) = temp2&
ELSE
number1(j%) = temp&
EXIT SUB
END IF
LOOP
END SUB

FUNCTION binary.convert$ (string1b$)
len.number2b% = LEN(string1b$) * 4
len.number1m% = LEN(string1m$)
n% = 9 - LEN(string1b$) MOD 9
IF n% <> 9 THEN string1b$ = STRING$(n%, "0") + string1b$
len.number1b% = LEN(string1b$) / 9

REDIM number1b&(len.number1b%)
REDIM number2b%(len.number2b%)

j% = 1: FOR I% = 1 TO len.number1b%
number1b&(I%) = VAL(MID$(string1b$, j%, 9))
j% = j% + 9: NEXT I%

j% = 0: FOR I% = 1 TO len.number1b%
DO
IF number1b&(I%) <= 0 THEN EXIT DO
j% = j% + 1
number2b%(j%) = number1b&(I%) AND 1
number1b&(I%) = number1b&(I%) \ 2
LOOP
NEXT I%

REDIM number1b&(1 TO 1)
FOR I% = j% TO 1 STEP -1: bin1$ = bin1$ + LTRIM$(STR$(number2b%(I%))): NEXT I%
REDIM number2b%(1 TO 1)

binary.convert$ = bin1$
END FUNCTION

SUB bit.draw (string1$, x1%, y1%)
FOR I% = 1 TO LEN(string1$)
IF MID$(string1$, I%, 1) = "1" THEN PSET (x1% + I%, y1%)
NEXT I%
END SUB

SUB factorial (n%)
temp$ = LTRIM$(STR$(n%))
FOR I% = n% - 1 TO 2 STEP -1
i2$ = LTRIM$(STR$(I%))
temp$ = multiply((temp$), (i2$))
'PRINT I%
bit.draw binary.convert$(temp$), 20, 20 + I%

NEXT I%
'PRINT temp$
END SUB

SUB factorial.bignum2a (n%)
IF n% > 99 THEN
len.number1m% = 2
REDIM number1m(1 TO len.number1m%) AS INTEGER
number1m%(1) = n% MOD 100
number1m%(1) = n%
temp2& = temp& MOD 100
carry% = (temp& - temp2&) / 10000
number1m%(2) = temp2&

ELSE
len.number1m% = 1
END IF
PRINT "Y"
SYSTEM
REDIM number1m(1 TO len.number1m%) AS INTEGER
REDIM number2m(1 TO len.number2m%) AS INTEGER

I% = n%
number1m%(1) = I%
number2m%(1) = I% - 1
multiply2a
'PRINT number1m%(1)
'PRINT number1m%(2)
'PRINT number1%(2)
SYSTEM
'FOR i% = n% TO 2 STEP -1
'i2$ = LTRIM$(STR$(i%))
'temp$ = multiply.bignum2((temp$), (i2$))
'PRINT i%
'NEXT i%
'PRINT temp$
END SUB

FUNCTION multiply$ (string1m$, string2m$)
len.number1m% = LEN(string1m$)
len.number2m% = LEN(string2m$)
IF len.number1m% = len.number2m% THEN
len.number1m% = len.number1m% + 1: len.number2m% = len.number2m% + 1
string1m$ = "0000" + string1m$: string2m$ = "0000" + string2m$
ELSE
IF len.number1m% > len.number2m% THEN
string1m$ = "0000" + string1m$
ELSE
string2m$ = "0000" + string2m$
END IF
END IF
diff4% = 4 - LEN(string1m$) MOD 4: IF diff4% <> 4 THEN string1m$ = STRING$(diff4%, "0") + string1m$
diff4% = 4 - LEN(string2m$) MOD 4: IF diff4% <> 4 THEN string2m$ = STRING$(diff4%, "0") + string2m$
len.number1m% = LEN(string1m$) / 4
len.number2m% = LEN(string2m$) / 4

REDIM number1m(1 TO len.number1m%) AS INTEGER
REDIM number2m(1 TO len.number2m%) AS INTEGER
j% = len.number1m% * 4 - 3: FOR I% = 1 TO len.number1m%
number1m(I%) = VAL(MID$(string1m$, j%, 4)): j% = j% - 4
NEXT I%
j% = len.number2m% * 4 - 3: FOR I% = 1 TO len.number2m%
number2m(I%) = VAL(MID$(string2m$, j%, 4)): j% = j% - 4
NEXT I%

multiply2a

FOR I% = len.number1% TO 1 STEP -1
temp$ = LTRIM$(STR$(number1(I%)))
n% = 4 - LEN(temp$) MOD 4
IF n% <> 4 THEN temp$ = STRING$(n%, "0") + temp$
temp2$ = temp2$ + temp$
NEXT I%

REDIM number1(1 TO 1) AS INTEGER, number2(1 TO 1) AS INTEGER
REDIM number1m(1 TO 1) AS INTEGER, number2m(1 TO 1) AS INTEGER
DO
IF MID$(temp2$, 1, 1) <> "0" THEN EXIT DO
temp2$ = MID$(temp2$, 2, LEN(temp2$))
LOOP
multiply$ = temp2$
END FUNCTION

SUB multiply2a
IF len.number1m% > len.number2m% THEN
len.number1% = len.number1m% + len.number2m%
len.number2% = len.number1m% + 1
REDIM number1(1 TO len.number1%) AS INTEGER
FOR I% = 1 TO len.number2m%
REDIM number2(1 TO len.number2%) AS INTEGER
IF number2m%(I%) <> 0 THEN
n1% = number2m%(I%)
FOR j% = 1 TO len.number1m%
IF carry% <> 0 OR number1m%(j%) <> 0 THEN
temp& = number1m%(j%) * CDBL(n1%) + carry%
IF temp& > 9999 THEN
temp2& = temp& MOD 10000
carry% = (temp& - temp2&) / 10000
number2%(j%) = temp2&
ELSE
number2%(j%) = temp&
carry% = 0
END IF
END IF
NEXT j%
GOSUB add.sub1
END IF
NEXT I%
EXIT SUB
END IF

len.number1% = len.number1m% + len.number2m%
len.number2% = len.number2m% + 1
REDIM number1(1 TO len.number1%) AS INTEGER
FOR I% = 1 TO len.number1m%
REDIM number2(1 TO len.number2%) AS INTEGER
IF number1m%(I%) <> 0 THEN
n1% = number1m%(I%)
FOR j% = 1 TO len.number2m%
IF carry% <> 0 OR number2m%(j%) <> 0 THEN
temp& = number2m%(j%) * CDBL(n1%) + carry%
IF temp& > 9999 THEN
temp2& = temp& MOD 10000
carry% = (temp& - temp2&) / 10000
number2%(j%) = temp2&
ELSE
number2%(j%) = temp&
carry% = 0
END IF
END IF
NEXT j%
GOSUB add.sub1
END IF
NEXT I%
EXIT SUB

add.sub1:
IF carry% <> 0 THEN number2(j%) = carry%: carry% = 0
diff2% = I% - 1
FOR i2% = 1 TO len.number2%
j% = i2% + diff2%
IF carry% = 0 THEN
IF number2(i2%) = 0 THEN GOTO skipmb2a
IF number1(j%) = 0 THEN number1(j%) = number2(i2%): GOTO skipmb2a
temp& = number1(j%) + number2(i2%)
ELSE
temp& = number1(j%) + number2(i2%) + carry%
END IF
IF temp& > 9999 THEN
temp2& = temp& MOD 10000
carry% = (temp& - temp2&) / 10000
number1(j%) = temp2&
ELSE
number1(j%) = temp&
carry% = 0
END IF
skipmb2a:
NEXT i2%

IF carry% <> 0 THEN
j% = len.number2% + I%
DO
j% = j% + 1
temp& = number1%(j%) + carry%
IF temp& > 9999 THEN
temp2& = temp& MOD 10000
carry% = (temp& - temp2&) MOD 10000
number1(j%) = temp2&
ELSE
number1(j%) = temp&
carry% = 0
EXIT DO
END IF
LOOP
END IF
RETURN
END SUB

[oracle]

Good... you and neo get into competition then I can have a lib war on my website!

[Agamemnus]

I am now using integers and long integer arrays instead of strings. In fact, I have two functions per operation: one that converts a number string to an integer array and runs the other one then converts the array back to a string. Even doing this slow conversion 2000 times in the factorial function,

2000! = < 40 seconds compiled w/vbdos on my computer.

Either using Neo's factorial function or mine, the time it takes to calculate his 2000! is much longer. I haven't yet calculated how long because it takes so long to run!! hehehe...

As an example of the speed, my 200! takes less than .5 seconds compiled. Neo's takes a little over 7 seconds.

Now completed:
factorial
binary conversion
addition
multiplication

[Neo]

Argh, you have me.

I'll start with my BSI's very very soon

[Agamemnus]

*blink*



BSI? :? a test?