BIGNUM v 2.5 - Printable Version +- Qbasicnews.com (http://qbasicnews.com/newforum) +-- Forum: QBasic (http://qbasicnews.com/newforum/forum-4.html) +--- Forum: QB Projects (http://qbasicnews.com/newforum/forum-12.html) +--- Thread: BIGNUM v 2.5 (/thread-836.html) |
BIGNUM v 2.5 - Agamemnus - 05-12-2003 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 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 BIGNUM v 2.5 - oracle - 05-13-2003 Good... you and neo get into competition then I can have a lib war on my website! . - Agamemnus - 05-15-2003 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 BIGNUM v 2.5 - Neo - 05-19-2003 Argh, you have me. I'll start with my BSI's very very soon BIGNUM v 2.5 - Agamemnus - 05-21-2003 *blink* BSI? :? a test? |