BigInt Class

[troycheek]

So, I was playing around with creating/verifying prime numbers with GB32.  I discovered that the largest integer number you can store in an Int64 aka Large variable is 2^63-1 or about 9 quintillion which is defined by the constant _maxLarge.  (It's possible GB32 uses temporary larger values internally when performing calculations, but that's the largest it can store in a variable.)  While 9x10^18 seems like a huge number to me, in prime number circles this is apparently a "very small number."  In contrast, the largest known prime number is 2^57 million or so, a number which is 17 million digits long.  Just calculating and displaying that number in GB32 would be non-trivial.

Digging around on the web, it seems that many languages have what is called a "BigInt Class" which is a set of routines for doing math on arbitrarily large integers.  I've not delved deeply into this, but my guess is that the BigInt method either "stacks" multiple Int64 variables (creating what is effectively Int128 or higher) or puts the individual digits in a numeric/string array and operates on each digit independently like grade school long division.  Since I can create a string 256 million bytes long, I could probably create some routines to add/subtract/multiply/divide them as numbers.  That should be big enough to play with what prime number enthusiasts would call a "large prime."

However, before I start digging into this, I thought I would check here to see if there are any GB32 keywords for dealing with larger integers that I'm overlooking, and to see if anyone has already implemented some BigInt routines in GFA.  Maybe there's a BigInt C DLL I could import and use?

Edit: If I've done this right, the largest prime you can "easily" calculate with GB32 is 9223372036854775783 or 2^63-25.  I started with _maxLarge (2^63-1) and worked my way down.

[dragonjim]

I seem to remember some time back someone broached the subject of handling Int128 variables and some functions were attempted, but what came of them I can neither remember nor find any trace; the only examples I could find refer to IBAN banking numbers but these appear to be bug-ridden and would not suit your purpose.

As for in-built variable types, GB32 sadly does not offer them; even more annoying is that the x86 assembly instructions handling quadwords (e.g. paddq and psubq) are not supported either (although you may have some luck with the add or sub assembly commands).

You could look for C-based dll's but you would stuck with the problem that GB32 does not have a variable into which to import any result exceeding _maxLarge.

Which leaves you with your idea of using strings which could actioned in two ways: firstly, with each byte as a digit, so 1,234,567,890,123,456,789 would take up 19 bytes; or, mimic how GB32 (and every other computer language) handles numbers and store it in a 16-byte long string and use the basic assembly or bit-shifting functions to perform the arithmetic operations.

I'm sorry I can not be of more help here.

If you make any progress or run into problems with this, please let me know.

[troycheek]

I suggested a C-based solution because FreeImage worked so well for another problem I had. I did not consider how I would store the results of a calculation exceeding _maxLarge. I guess I just assumed it would be stored in a string or a variant. (I don't really understand variants, I just know they store values differently than set variable types.)

I was doing some back of the eyelid calculations last night (translation: thinking about programming while drifting off to sleep) and I think that a string with each byte as a digit would be the way to go. An Int128 class would only give me about 38 digits (and doubling the bytes doubles the digits), but a byte as a digit string class could handle numbers with hundreds/thousands/millions of digits in one fell swoop. And I think (please confirm this for me) that I really only need to write AddBigNum and SubBigNum functions, as integer multiplication is just a bunch of iterative Add functions, and integer division is just a bunch of iterative Sub functions. For prime number research, what I really need is a good Mod function, and that would be even easier to program than Div.

However, I recently discovered that prime number researchers tend to focus on finding the largest primes or primes that fit a certain pattern (2^N-1) because they are easier to factor, instead of calculating every prime up to a certain number, so it's just barely possible there's an undocumented prime smaller than _maxLarge.

[dragonjim]

Briefly (and I think I'm correct in saying this) variants are objects that can hold any variable type, OCX object, picture (not handled well in GB32) or Type structure...and they could be the answer that you are looking for. The MSDN website says: Numeric data can be any integer or real number value ranging from -1.797693134862315E308 to -4.94066E-324 for negative values and from 4.94066E-324 to 1.797693134862315E308 for positive values.

And the small program below shows that this property is inherited by GB32:

Dim a As Variant
a = 10 ^ 308
Print a
Print a / 10
Print a / 10 * 5

Is 10³⁰⁸ big enough?

That said, all the variant is doing is reproducing a Double variable, so you could always use that instead...

[troycheek]

The problem with Double variables is that they're floating point and only hold 15 or 16 decimals of precision. To GB32, 1.2345E99+100=1.2345E99 or so I hear. When crunching prime numbers, you need precision all the way down to the one's place.

[lab]

Hi Troycheck
Here is some biginteger math functions, they are arbitrary so you can choose as many ciffers as you want.
routines are quite fast, n'bit math is proportionally slower with size of biginteger. I still develop these to better handle mul and div

Regards, Lasse Bauer

CODE:

' Base32 bigintegers, number limit BMAX% is dependent on memory only
' numbers are held in string type. feel free to use and modify and publish / LB.
'
' Functions:
' badd: adds two bigintegers
' bsub: subtracts two bigintegers
' bmul: multiply biginteger with 32 bit value
' bdiv: divide biginteger with 32 bit value
' dec2big: create big integer from string in base10
' big2dec: create string base10 from base2^32
' big2hex: create string base16 from base2^32
'
' change BMAX% to desired value, eg:
' BMAX%=4 for 128 bit integers
' BMAX%=32 for 1024 bit integers ~ 10^77
' BMAX%=1000 for 32000 bit integers ~ 10^9700
' Use $stepoff directive when using intensive

Global BMAX% = 8 ' # of 32 bit digits allocated, memory needed= BMAX%*4+4 bytes per number
Global DMAX%
If BMAX% < 512
DMAX% = Ceil(Log10(Exp2(BMAX% * 32))) 'number of ciffers in base10 to display a base2^32 number
Else
' default if above overflows
DMAX% = 10 * BMAX%
EndIf



Debug.Show

Debug "declaring a bigint","99999999990000000000000000000000000000000000001"
Local x$ = dec2big("99999999990000000000000000000000000000000000001")
Debug "in decimal: ",big2dec(x$)
Debug "in hexadecimal:",big2hex(x$)


Debug
Debug
Debug "Addition two bigintegers"

Local y$ = dec2big("111111111111111111111")
Debug big2dec(y$)
Debug "+"
Debug big2dec(x$)
Debug "="
badd(x$, y$)
Debug big2dec(x$)

Debug "division bigintegers/integer"
Debug
Debug big2dec(y$)
Debug "/ 2 ="
bdiv(y$, 2)
Debug big2dec(y$)

Debug
Debug "mulitiplication bigintegers*integer"
Debug big2dec(y$)
Debug "* 20000 ="
bmul(y$, 20000)
Debug big2dec(y$)
Debug

Debug "subtraction two bigintegers"
Debug big2dec(x$)
Debug "-"
Debug big2dec(y$)
Debug "="
bsub(x$, y$)
Debug big2dec(x$)
Debug

Debug "validation of subtraction:"
Debug big2dec(x$)
Debug "+"
Debug big2dec(y$)
Debug "="
badd(x$, y$)
Debug big2dec(x$)
Debug


Function big2dec(bigint$)
' convert base2^32 to base10
Local i, d
Local o$ = ""
For i = 0 To DMAX% - 1 ' Log10(Exp2(BMAX% * 32))
' For i = 0 To BMAX% * 12 'todo, need to find 'proper length after conversion
d = bdiv(bigint$, 10)
o$ = Format( d) + o$
Next
Return o$
EndFunc


Function dec2big(decnum$)
' convert base10 to base2^32

Local i
Local srcval% = 0
Local src% = V:srcval%
Local retval$ = String(BMAX% * 4 + 4 , 0)
Local addval$ = String(BMAX% * 4 + 4, 0)
For i = 1 To Len(decnum$)
bmul(retval$, 10)
LPoke V:addval$ , Val(Mid$(decnum$, i, 1))
badd(retval$, addval$)
Next i
Return retval$
EndFunc

Function big2hex(ByRef bigint$)
Local hb
Local hx$ = ""
For hb = 0 To BMAX%
hx$ = Hex$(LPeek(V:bigint$ + hb * 4), 8) + " " + hx$
Next hb
Return hx$
EndFunction


Proc badd(ByRef dest$, ByRef src$) ' dest=biginteger dest+biginteger src%
$StepOff

Local src% = V:src$
Local dest% = V:dest$
. mov esi, src%
. mov edi, dest%
. mov ecx, BMAX%

. mov eax, [ esi]
. add [ edi], eax
.baddl:
. mov eax, [ esi+4]
. adc [ edi+4], eax
. add esi, 4
. add edi, 4
. loop .baddl

. jc .addoverflow
. jmp .goodadd
.addoverflow:
Stop
.goodadd:
EndProc



Proc bsub(ByRef dest$, ByRef src$) ' dest=biginteger dest-biginteger src%
' ?todo: improve to do complement addition
$StepOff

Local src% = V:src$
Local dest% = V:dest$
. mov esi, src%
. mov edi, dest%
. mov ecx, BMAX%

. mov eax, [ esi]
. sub [ edi], eax
.bsubl:
. mov eax, [ esi+4 ]
. sbb [ edi+4 ], eax
. add esi, 4
. add edi, 4
. loop .bsubl

. jc .subunderflow
. jmp .goodsub
.subunderflow:
Stop
.goodsub:
EndProc

Proc bmul(ByRef dest$, factor%) ' dest=biginteger dest*32 bit factor%
$StepOff

Local dest% = V:dest$
. mov esi, factor%
. mov edi, dest%
. mov ecx, BMAX%

. mov eax, [ edi]
. mul esi
. mov [ edi], eax
. mov ebx, edx

.bmull:
. add edi, 4
. mov eax, [ edi]
. mul esi
. add eax, ebx
. mov [ edi], eax
. mov ebx, edx
. loop .bmull

. cmp edx, 0
. jne .overflowbmul
. jmp .bmulok
.overflowbmul:
' Stop
.bmulok:
EndProc


Function bdiv(ByRef dest$, divisor%) ' dest=biginteger dest/32 bit divisor%
' todo: fix results false when divisor divisor% is bigger than dest%
'
$StepOff
Local dest% = V:dest$
. mov esi, divisor%
. mov edi, dest%
. mov ecx, BMAX%

. add edi, ecx
. add edi, ecx
. add edi, ecx
. add edi, ecx

. mov edx, 0

.bdivl:
. mov eax, [ edi]
. div esi
. mov [ edi], eax
. sub edi, 4
. cmp edi, dest%
. jge .bdivl
GetRegs
Return _EDX
EndFunction

[dragonjim]

These are brilliant and extremely flexible...thank you for sharing them.