128-bit integer division

[srvaldez]

deltarho[1859] sometimes needs 128-bit integers and I thought about writing a library but there are some stompers on the road
1: how to efficiently do 128-bit integer division with remainder
2: how to handle multiplication overflow

here's one that you could possibly restrict to 128-bits but I don't like the division algorithm used https://github.com/kokke/tiny-bignum-c

I scoured the web but there's no one solution that is satisfactory, sometimes it's the license and/or it's 64-bit only
any thoughts?

[dodicat]

Try this one srvaldez.
Licence to ROFL.

Code: Select all

Function _divide(n1 As String,n2 As String,decimal_places As integer=10,dpflag As String="s") As String
          Dim As String number=n1,divisor=n2
          dpflag=lcase(dpflag)
          'For MOD
          dim as integer modstop
          if dpflag="mod" then 
              if len(n1)<len(n2) then return n1
              if len(n1)=len(n2) then
                  if n1<n2 then return n1
                  end if
              modstop=len(n1)-len(n2)+1
              end if
          if dpflag<>"mod" then
     If dpflag<>"s"  Then dpflag="raw" 
     end if
        Dim runcount As integer
        '_______  LOOK UP TABLES ______________
        Dim Qmod(0 To 19) As Ubyte
        Dim bool(0 To 19) As Ubyte
        For z As Integer=0 To 19
    Qmod(z)=(z Mod 10+48)
    bool(z)=(-(10>z))
Next z
Dim answer As String   'THE ANSWER STRING  

'_______ SET THE DECIMAL WHERE IT SHOULD BE AT _______
Dim As String part1,part2
#macro set(decimal)
#macro insert(s,char,position)
If position > 0 And position <=Len(s) Then
part1=Mid$(s,1,position-1)
part2=Mid$(s,position)
s=part1+char+part2
End if
#endmacro
insert(answer,".",decpos)
  answer=thepoint+zeros+answer
If dpflag="raw" Then
    answer=Mid(answer,1,decimal_places)
    End if
#endmacro
'______________________________________________
'__________ SPLIT A STRING ABOUT A CHARACTRR __________
Dim As String var1,var2
    Dim pst As integer
      #macro split(stri,char,var1,var2)
    pst=Instr(stri,char)
    var1="":var2=""
    If pst<>0 Then
    var1=Rtrim(Mid(stri,1,pst),".")
    var2=Ltrim(Mid(stri,pst),".")
Else
    var1=stri
    End if
    #endmacro
    
       #macro Removepoint(s)
       split(s,".",var1,var2)
#endmacro
'__________ GET THE SIGN AND CLEAR THE -ve __________________
Dim sign As String
          If Left(number,1)="-" Xor Left (divisor,1)="-" Then sign="-"
            If Left(number,1)="-" Then  number=Ltrim(number,"-")
            If Left (divisor,1)="-" Then divisor=Ltrim(divisor,"-")
              
'DETERMINE THE DECIMAL POSITION BEFORE THE DIVISION
Dim As integer lennint,lenddec,lend,lenn,difflen
split(number,".",var1,var2)
lennint=Len(var1)
split(divisor,".",var1,var2)
lenddec=Len(var2)

If Instr(number,".") Then 
    Removepoint(number)
    number=var1+var2
    End if
If Instr(divisor,".") Then 
    Removepoint(divisor)
    divisor=var1+var2
    End if
Dim As integer numzeros
numzeros=Len(number)
number=Ltrim(number,"0"):divisor=Ltrim (divisor,"0")
numzeros=numzeros-Len(number)
lend=Len(divisor):lenn=Len(number)
If lend>lenn Then difflen=lend-lenn
Dim decpos As integer=lenddec+lennint-lend+2-numzeros 'THE POSITION INDICATOR
Dim _sgn As Byte=-Sgn(decpos)
If _sgn=0 Then _sgn=1
Dim As String thepoint=String(_sgn,".") 'DECIMAL AT START (IF)
Dim As String zeros=String(-decpos+1,"0")'ZEROS AT START (IF) e.g. .0009
if dpflag<>"mod" then
If Len(zeros) =0 Then dpflag="s"
end if
Dim As integer runlength
If Len(zeros) Then 
     runlength=decimal_places
     answer=String(Len(zeros)+runlength+10,"0")
    If dpflag="raw" Then 
        runlength=1
        answer=String(Len(zeros)+runlength+10,"0")
        If decimal_places>Len(zeros) Then
            runlength=runlength+(decimal_places-Len(zeros))
            answer=String(Len(zeros)+runlength+10,"0")
            End If
            End If

Else
decimal_places=decimal_places+decpos
runlength=decimal_places
answer=String(Len(zeros)+runlength+10,"0")
End if
'___________DECIMAL POSITION DETERMINED  _____________

'SET UP THE VARIABLES AND START UP CONDITIONS
number=number+String(difflen+decimal_places,"0")
        Dim count As integer
        Dim temp As String
        Dim copytemp As String
        Dim topstring As String
        Dim copytopstring As String
        Dim As integer lenf,lens
        Dim As Ubyte takeaway,subtractcarry
        Dim As integer n3,diff
       If Ltrim(divisor,"0")="" Then Return "Error :division by zero"   
        lens=Len(divisor)
         topstring=Left(number,lend)
         copytopstring=topstring
        Do
            count=0
        Do
            count=count+1
            copytemp=temp
    
            Do
'___________________ QUICK SUBTRACTION loop _________________              
            
lenf=Len(topstring)
If  lens<lenf=0 Then 'not
If Lens>lenf Then
temp= "done"
Exit Do
End if
If divisor>topstring Then 
temp= "done"
Exit Do
End if
End if

  diff=lenf-lens
        temp=topstring
        subtractcarry=0
        
        For n3=lenf-1 To diff Step -1
            takeaway= topstring[n3]-divisor[n3-diff]+10-subtractcarry
            temp[n3]=Qmod(takeaway)
            subtractcarry=bool(takeaway)
        Next n3 
        If subtractcarry=0 Then Exit Do
         If n3=-1 Then Exit Do
        For n3=n3 To 0 Step -1 
            takeaway= topstring[n3]-38-subtractcarry
             temp[n3]=Qmod(takeaway)
            subtractcarry=bool(takeaway)
            if subtractcarry=0 then exit do
            Next n3
        Exit Do
        
        Loop 'single run
        temp=Ltrim(temp,"0")
        If temp="" Then temp= "0"
            topstring=temp
        Loop Until temp="done"
     ' INDIVIDUAL CHARACTERS CARVED OFF ________________       
        runcount=runcount+1
       If count=1 Then
           topstring=copytopstring+Mid(number,lend+runcount,1)
           Else
       topstring=copytemp+Mid(number,lend+runcount,1)
   End If
       copytopstring=topstring
       topstring=Ltrim(topstring,"0")
       if dpflag="mod" then
       if runcount=modstop then 
           if topstring="" then return "0"
           return mid(topstring,1,len(topstring)-1)
           end if
       end if
       answer[runcount-1]=count+47
       If topstring="" And runcount>Len(n1)+1 Then
           Exit Do
           End if
   Loop Until runcount=runlength+1
   
   ' END OF RUN TO REQUIRED DECIMAL PLACES
   set(decimal) 'PUT IN THE DECIMAL POINT
  'THERE IS ALWAYS A DECIMAL POINT SOMEWHERE IN THE ANSWER
  'NOW GET RID OF IT IF IT IS REDUNDANT
       answer=Rtrim(answer,"0")
       answer=Rtrim(answer,".")
       answer=Ltrim(answer,"0")
       If answer="" Then Return "0"
   Return sign+answer
End Function



#define mod_(a,b) _divide((a),(b),,"mod")
#define div_(a,b) iif(len((a))<len((b)),"0",_divide((a),(b),-2))
'=======================================================================
#define Intrange(f,l) int(Rnd*(((l)+1)-(f))+(f))

type answer
      as string quotient,remainder
end type

function longdivide(numerator as string,denominator as string) as answer
      dim as answer a
      a.quotient=div_(numerator,denominator)
      a.remainder=mod_(numerator,denominator)
      return a
end function

print "test a few small numbers"
dim as answer x
for n as long=1 to 10
      var numerator=str(intrange(100,10000))
      var denominator=str(intrange(30,99))
      print numerator;" / ";denominator
x=longdivide(numerator,denominator)
print  x.quotient; "  remainder ";x.remainder
print "check ";val(x.quotient)*val(denominator)+val(x.remainder)
print "-----------"
next
print "press a key"
sleep

var numerator=  "999999999999999999998888888888888888"
var denominator="18446744073709551616"
      print numerator;" / ";denominator
      x=longdivide(numerator,denominator)
      print  x.quotient; "  remainder ";x.remainder
      sleep
      
 

[srvaldez]

thank you dodicat
with the help of FBfrog I translated the code at https://github.com/kokke/tiny-bignum-c
all seems to be working except the bignum_from_string and the bignum_to_string functions
code need to cleaned up, not sure about all the asserts and of course we need conversions to/from string<-->bignum
if you or anyone cares to have a look, here it is
I set the size to 128-bits in the const BN_ARRAY_SIZE = 16 / WORD_SIZE statement
BTW the code is in the public domain as in do whatever you want with it

Code: Select all

#pragma once

#include once "crt/stdio.bi"
#include once "crt/stdint.bi"

#define __BIGNUM_H__
const WORD_SIZE = 4
const BN_ARRAY_SIZE = 16 / WORD_SIZE
type DTYPE as ulong
type DTYPE_TMP as ulongint
#define DTYPE_MSB DTYPE_TMP(&h80000000)
#define SPRINTF_FORMAT_STR "%.08x"
#define SSCANF_FORMAT_STR "%8x"
#define MAX_VAL &hFFFFFFFFull
#define require(p, msg) assert(-(p andalso msg))

dim shared as boolean overflow

type bn
	array(0 to BN_ARRAY_SIZE - 1) as ulong
end type

enum
	SMALLER = -1
	EQUAL = 0
	LARGER = 1
end enum

declare sub bignum_init(byref n as bn)
declare sub bignum_from_int(byref n as bn, byval i as ulongint)
declare function bignum_to_int(byref n as bn) as long
declare sub bignum_from_string(byref n as bn, byref as string, byval nbytes as long)
declare sub bignum_to_string(byref n as bn, byref as string, byval maxsize as long)
declare sub bignum_add(byref a as bn, byref b as bn, byref c as bn)
declare sub bignum_sub(byref a as bn, byref b as bn, byref c as bn)
declare sub bignum_mul(byref a as bn, byref b as bn, byref c as bn)
declare sub bignum_div(byref a as bn, byref b as bn, byref c as bn)
declare sub bignum_mod(byref a as bn, byref b as bn, byref c as bn)
declare sub bignum_divmod(byref a as bn, byref b as bn, byref c as bn, byref d as bn)
declare sub bignum_and(byref a as bn, byref b as bn, byref c as bn)
declare sub bignum_or(byref a as bn, byref b as bn, byref c as bn)
declare sub bignum_xor(byref a as bn, byref b as bn, byref c as bn)
declare sub bignum_lshift(byref a as bn, byref b as bn, byval nbits as long)
declare sub bignum_rshift(byref a as bn, byref b as bn, byval nbits as long)
declare function bignum_cmp(byref a as bn, byref b as bn) as long
declare function bignum_is_zero(byref n as bn) as long
declare sub bignum_inc(byref n as bn)
declare sub bignum_dec(byref n as bn)
declare sub bignum_pow(byref a as bn, byref b as bn, byref c as bn)
declare sub bignum_isqrt(byref a as bn, byref b as bn)
declare sub bignum_assign(byref dst as bn, byref src as bn)
declare sub _lshift_one_bit(byref a as bn)
declare sub _rshift_one_bit(byref a as bn)
declare sub _lshift_word(byref a as bn, byval nwords as long)
declare sub _rshift_word(byref a as bn, byval nwords as long)

private sub bignum_init(byref n as bn)
	'assert(-(n andalso "n is null"))
	dim i as long
	for i = 0 to BN_ARRAY_SIZE-1
		n.array(i) = 0
	next
end sub

private sub bignum_from_int(byref n as bn, byval i as ulongint)
	'assert(-(n andalso "n is null"))
	bignum_init(n)
	n.array(0) = i
	dim num_32 as ulongint = 32
	dim tmp as ulongint = i shr num_32
	n.array(1) = tmp
end sub

private function bignum_to_int(byref n as bn) as long
	dim ret as long = 0
	ret += n.array(0)
	return ret
end function

private sub bignum_from_string(byref n as bn, byref st as string, byval nbytes as long)
	'assert(-(n andalso "n is null"))
	'assert(-(str andalso "str is null"))
	'assert(-((nbytes > 0) andalso "nbytes must be positive"))
	'assert(-(((nbytes and 1) = 0) andalso "string format must be in hex -> equal number of bytes"))
	'assert(-(((nbytes mod (sizeof(ulong) * 2)) = 0) andalso "string length must be a multiple of (sizeof(DTYPE) * 2) characters"))
	bignum_init(n)
	dim tmp as ulong
	dim i as long = nbytes - (2 * 4)
	dim j as long = 0
	while i >= 0
		tmp = 0
		sscanf(@st[i], "%8x", @tmp)
		n.array(j) = tmp
		i -= 2 * 4
		j += 1
	wend
end sub

private sub bignum_to_string(byref n as bn, byref st as string, byval nbytes as long)
	'assert(-(n andalso "n is null"))
	'assert(-(str andalso "str is null"))
	'assert(-((nbytes > 0) andalso "nbytes must be positive"))
	'assert(-(((nbytes and 1) = 0) andalso "string format must be in hex -> equal number of bytes"))
	dim j as long = BN_ARRAY_SIZE - 1
	dim i as long = 0
	while (j >= 0) andalso (nbytes > (i + 1))
		sprintf(@st[i], "%.08x", @n.array(j))
		i += 2 * 4
		j -= 1
	wend
	j = 0
	while st[j] = asc("0")
		j += 1
	wend
	for i = 0 to (nbytes - j)-1
		st[i] = st[i + j]
	next
	st[i] = 0
end sub

private sub bignum_dec(byref n as bn)
	'' assert(-(n andalso "n is null"))
	dim tmp as ulong
	dim res as ulong
	dim i as long
	for i = 0 to BN_ARRAY_SIZE-1
		tmp = n.array(i)
		res = tmp - 1
		n.array(i) = res
		if (not(res > tmp)) then exit for
	next
end sub

private sub bignum_inc(byref n as bn)
	'' assert(-(n andalso "n is null"))
	dim res as ulong
	dim tmp as ulongint
	dim i as long
	for i = 0 to BN_ARRAY_SIZE-1
		tmp = n.array(i)
		res = tmp + 1
		n.array(i) = res
		if (res > tmp) then exit for
	next
end sub

private sub bignum_add(byref a as bn, byref b as bn, byref c as bn)
	'' assert(-(a andalso "a is null"))
	'' assert(-(b andalso "b is null"))
	'' assert(-(c andalso "c is null"))
	dim tmp as ulongint
	dim carry as long = 0
	dim i as long
	for i = 0 to BN_ARRAY_SIZE-1
		tmp = cast(ulongint, a.array(i)) + b.array(i) + carry
		carry = (tmp > (cast(ulongint,&hFFFFFFFF)))
		c.array(i) = (tmp and (cast(ulongint,&hFFFFFFFF)))
	next
end sub

private sub bignum_sub(byref a as bn, byref b as bn, byref c as bn)
	'' assert(-(a andalso "a is null"))
	'' assert(-(b andalso "b is null"))
	'' assert(-(c andalso "c is null"))
	dim res as ulongint
	dim tmp1 as ulongint
	dim tmp2 as ulongint
	dim borrow as long = 0
	dim i as long
	for i = 0 to BN_ARRAY_SIZE-1
		tmp1 = cast(ulongint, a.array(i)) + ((cast(ulongint, &hFFFFFFFF)) + 1)
		tmp2 = cast(ulongint, b.array(i)) + borrow
		res = (tmp1 - tmp2)
		c.array(i) = cast(ulong, (res and (cast(ulongint, &hFFFFFFFF))))
		borrow = (res <= (cast(ulongint, &hFFFFFFFF)))
	next
end sub

private sub bignum_mul(byref a as bn, byref b as bn, byref c as bn)
	'assert(-(a andalso "a is null"))
	'assert(-(b andalso "b is null"))
	'assert(-(c andalso "c is null"))
	dim row as bn
	dim tmp as bn
	dim i as long
	dim j as long
	bignum_init(c)
	for i = 0 to BN_ARRAY_SIZE-1
		bignum_init(row)
		for j = 0 to BN_ARRAY_SIZE-1
			if (i + j < BN_ARRAY_SIZE) then
				bignum_init(tmp)
				dim as ulongint intermediate = (cast(ulongint, a.array(i)) * cast(ulongint,b.array(j)))
				bignum_from_int(tmp, intermediate)
				_lshift_word(tmp, i + j)
				bignum_add(tmp, row, row)
			end if
		next
		bignum_add(c, row, c)
	next
end sub

private sub bignum_div(byref a as bn, byref b as bn, byref c as bn)
	'' assert(-(a andalso "a is null"))
	'' assert(-(b andalso "b is null"))
	'' assert(-(c andalso "c is null"))
	dim current as bn
	dim denom as bn
	dim tmp as bn
	bignum_from_int(current, 1)
	bignum_assign(denom, b)
	bignum_assign(tmp, a)
	dim half_max as const ulongint = 1 + culngint(culngint(&hFFFFFFFF) / 2)
	overflow = false
	while bignum_cmp(denom, a) <> LARGER
		if denom.array((BN_ARRAY_SIZE - 1)) >= half_max then
			overflow = true
			exit while
		end if
		_lshift_one_bit(current)
		_lshift_one_bit(denom)
	wend
	if overflow = 0 then
		_rshift_one_bit(denom)
		_rshift_one_bit(current)
	end if
	bignum_init(c)
	while bignum_is_zero(current) = 0
		if bignum_cmp(tmp, denom) <> SMALLER then
			bignum_sub(tmp, denom, tmp)
			bignum_or(c, current, c)
		end if
		_rshift_one_bit(current)
		_rshift_one_bit(denom)
	wend
end sub

private sub bignum_lshift(byref a as bn, byref b as bn, byval nbits as long)
	'' assert(-(a andalso "a is null"))
	'' assert(-(b andalso "b is null"))
	'' assert(-((nbits >= 0) andalso "no negative shifts"))
	bignum_assign(b, a)
	dim nbits_pr_word as const long = 4 * 8
	dim nwords as long = nbits / nbits_pr_word
	if nwords <> 0 then
		_lshift_word(b, nwords)
		nbits -= nwords * nbits_pr_word
	end if
	if nbits <> 0 then
		dim i as long
		for i = BN_ARRAY_SIZE - 1 to 1 step -1
			b.array(i) = (b.array(i) shl nbits) or (b.array(i - 1) shr ((8 * 4) - nbits))
		next
		b.array(i) shl= nbits
	end if
end sub

private sub bignum_rshift(byref a as bn, byref b as bn, byval nbits as long)
	'' assert(-(a andalso "a is null"))
	'' assert(-(b andalso "b is null"))
	'' assert(-((nbits >= 0) andalso "no negative shifts"))
	bignum_assign(b, a)
	dim nbits_pr_word as const long = 4 * 8
	dim nwords as long = nbits / nbits_pr_word
	if nwords <> 0 then
		_rshift_word(b, nwords)
		nbits -= nwords * nbits_pr_word
	end if
	if nbits <> 0 then
		dim i as long
		for i = 0 to (BN_ARRAY_SIZE - 1)-1
			b.array(i) = (b.array(i) shr nbits) or (b.array(i + 1) shl ((8 * 4) - nbits))
		next
		b.array(i) shr= nbits
	end if
end sub

private sub bignum_mod(byref a as bn, byref b as bn, byref c as bn)
	'' assert(-(a andalso "a is null"))
	'' assert(-(b andalso "b is null"))
	'' assert(-(c andalso "c is null"))
	dim tmp as bn
	bignum_divmod(a, b, tmp, c)
end sub

private sub bignum_divmod(byref a as bn, byref b as bn, byref c as bn, byref d as bn)
	'' assert(-(a andalso "a is null"))
	'' assert(-(b andalso "b is null"))
	'' assert(-(c andalso "c is null"))
	dim tmp as bn
	bignum_div(a, b, c)
	bignum_mul(c, b, tmp)
	bignum_sub(a, tmp, d)
end sub

private sub bignum_and(byref a as bn, byref b as bn, byref c as bn)
	'' assert(-(a andalso "a is null"))
	'' assert(-(b andalso "b is null"))
	'' assert(-(c andalso "c is null"))
	dim i as long
	for i = 0 to BN_ARRAY_SIZE-1
		c.array(i) = (a.array(i) and b.array(i))
	next
end sub

private sub bignum_or(byref a as bn, byref b as bn, byref c as bn)
	'' assert(-(a andalso "a is null"))
	'' assert(-(b andalso "b is null"))
	'' assert(-(c andalso "c is null"))
	dim i as long
	for i = 0 to BN_ARRAY_SIZE-1
		c.array(i) = (a.array(i) or b.array(i))
	next
end sub

private sub bignum_xor(byref a as bn, byref b as bn, byref c as bn)
	'' assert(-(a andalso "a is null"))
	'' assert(-(b andalso "b is null"))
	'' assert(-(c andalso "c is null"))
	dim i as long
	for i = 0 to BN_ARRAY_SIZE-1
		c.array(i) = (a.array(i) xor b.array(i))
	next
end sub

private function bignum_cmp(byref a as bn, byref b as bn) as long
	'' assert(-(a andalso "a is null"))
	'' assert(-(b andalso "b is null"))
	dim i as long = 16 / 4
	do
		i -= 1
		if a.array(i) > b.array(i) then
			return LARGER
		elseif a.array(i) < b.array(i) then
			return SMALLER
		end if
	loop while i <> 0
	return EQUAL
end function

private function bignum_is_zero(byref n as bn) as long
	'' assert(-(n andalso "n is null"))
	dim i as long
	for i = 0 to BN_ARRAY_SIZE-1
		if n.array(i) then return 0
	next
	return 1
end function

private sub bignum_pow(byref a as bn, byref b as bn, byref c as bn)
	'' assert(-(a andalso "a is null"))
	'' assert(-(b andalso "b is null"))
	'' assert(-(c andalso "c is null"))
	dim tmp as bn
	bignum_init(c)
	if bignum_cmp(b, c) = EQUAL then
		bignum_inc(c)
	else
		dim bcopy as bn
		bignum_assign(bcopy, b)
		bignum_assign(tmp, a)
		bignum_dec(bcopy)
		while bignum_is_zero(bcopy) = 0
			bignum_mul(tmp, a, c)
			bignum_dec(bcopy)
			bignum_assign(tmp, c)
		wend
		bignum_assign(c, tmp)
	end if
end sub

private sub bignum_isqrt(byref a as bn, byref b as bn)
	'' assert(-(a andalso "a is null"))
	'' assert(-(b andalso "b is null"))
	dim low as bn
	dim high as bn
	dim midle as bn
	dim tmp as bn
	bignum_init(low)
	bignum_assign(high, a)
	bignum_rshift(high, midle, 1)
	bignum_inc(midle)
	while bignum_cmp(high, low) > 0
		bignum_mul(midle, midle, tmp)
		if bignum_cmp(tmp, a) > 0 then
			bignum_assign(high, midle)
			bignum_dec(high)
		else
			bignum_assign(low, midle)
		end if
		bignum_sub(high, low, midle)
		_rshift_one_bit(midle)
		bignum_add(low, midle, midle)
		bignum_inc(midle)
	wend
	bignum_assign(b, low)
end sub

private sub bignum_assign(byref dst as bn, byref src as bn)
	'' assert(-(dst andalso "dst is null"))
	'' assert(-(src andalso "src is null"))
	dim i as long
	for i = 0 to BN_ARRAY_SIZE-1
		dst.array(i) = src.array(i)
	next
end sub

private sub _rshift_word(byref a as bn, byval nwords as long)
	'' assert(-(a andalso "a is null"))
	'' assert(-((nwords >= 0) andalso "no negative shifts"))
	dim i as long
	if nwords >= BN_ARRAY_SIZE then
		for i = 0 to BN_ARRAY_SIZE-1
			a.array(i) = 0
		next
		exit sub
	end if
	for i = 0 to (BN_ARRAY_SIZE - nwords)-1
		a.array(i) = a.array(i + nwords)
	next
	while i < BN_ARRAY_SIZE
		a.array(i) = 0
		i+=1
	wend
end sub

private sub _lshift_word(byref a as bn, byval nwords as long)
	'' assert(-(a andalso "a is null"))
	'' assert(-((nwords >= 0) andalso "no negative shifts"))
	dim i as long
	for i = (BN_ARRAY_SIZE - 1) to nwords step -1
		a.array(i) = a.array(i - nwords)
	next
	while i >= 0
		a.array(i) = 0
		i-=1
	wend
end sub

private sub _lshift_one_bit(byref a as bn)
	'' assert(-(a andalso "a is null"))
	dim i as long
	for i = (BN_ARRAY_SIZE - 1) to 1 step -1
		a.array(i) = (a.array(i) shl 1) or (a.array(i - 1) shr ((8 * 4) - 1))
	next
	a.array(0) shl= 1
end sub

private sub _rshift_one_bit(byref a as bn)
	'' assert(-(a andalso "a is null"))
	dim i as long
	for i = 0 to (BN_ARRAY_SIZE - 1)-1
		a.array(i) = (a.array(i) shr 1) or (a.array(i + 1) shl ((8 * 4) - 1))
	next
	a.array((BN_ARRAY_SIZE - 1)) shr= 1
end sub

private sub factorial(byref n as bn, byref res as bn)
	dim tmp as bn
	bignum_assign(tmp, n)
	bignum_dec(n)
	while bignum_is_zero(n) = 0
		bignum_mul(tmp, n, res)
		bignum_dec(n)
		bignum_assign(tmp, res)
	wend
	bignum_assign(res, tmp)
end sub


	dim as bn num, result, tmp
	dim buf as zstring * 8192
	bignum_from_int(num, 12)
	factorial(num, result)
	'bignum_to_string(result, buf, sizeof(buf))
	printf(!"factorial(100) using bignum = %s\n", buf)
	printf(!"%d\n", sizeof(num))
? bignum_to_int(result)

bignum_from_int(num, 2000000000)
bignum_from_int(tmp, 1000000000)
bignum_mul(tmp, num, result)
bignum_isqrt(result, num)
? bignum_to_int(num)
bignum_from_int(tmp, 10)
bignum_div(num, tmp, result)
? bignum_to_int(result)
bignum_from_int(num, 2)
bignum_from_int(tmp, 30)
bignum_pow(num, tmp, result)
? bignum_to_int(result)
bignum_from_int(num, 3)
bignum_from_int(tmp, 19)
bignum_pow(num, tmp, result)
? bignum_to_int(result)

[dodicat]

In your function
private sub bignum_to_string(byref n as bn, byref st as zstring ptr, byval nbytes as long)
st has to be a zstring ptr as above.

Otherwise you get an empty string, thus string indexing fails.
You factorial is actually factorial(12) the way you have it.
? bignum_to_int(result) gives 479001600 which is correct.
Check big factorials.

Code: Select all

Function factorial(num As Long) As String
      Static As Ubyte _mod_(99)={48,49,50,51,52,53,54,55,56,57,48,49,50,51,52,53,54,55,56,57,48, _
      49,50,51,52,53,54,55,56,57,48,49,50,51,52,53,54,55,56,57,48, _
      49,50,51,52,53,54,55,56,57,48,49,50,51,52,53,54,55,56,57,48, _
      49,50,51,52,53,54,55,56,57,48,49,50,51,52,53,54,55,56,57,48, _
      49,50,51,52,53,54,55,56,57,48,49,50,51,52,53,54,55,56,57}
      Static As Ubyte _div_(99)={0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1, _
      2,2,2,2,2,2,2,2,2,2,3,3,3,3,3,3,3,3,3,3, _
      4,4,4,4,4,4,4,4,4,4,5,5,5,5,5,5,5,5,5,5, _
      6,6,6,6,6,6,6,6,6,6,7,7,7,7,7,7,7,7,7,7, _
      8,8,8,8,8,8,8,8,8,8,9,9,9,9,9,9,9,9,9,9}
      Dim As String fact="1",a,b,c
      Dim As Ubyte n,carry,ai
      Dim As Long la,lb
      For z As Long=1 To num
            a=fact:b=Str(z):la=Len(a):lb=Len(b):c=String(la+lb,"0")
            For i As Long =la-1 To 0 Step -1
                  carry=0:ai=a[i]-48
                  For j As Long =lb-1 To 0 Step -1
                        n =ai*(b[j]-48)+(c[i+j+1]-48)+carry
                        carry =_Div_(n):c[i+j+1]=_Mod_(n)
                  Next j
                  c[i]+=carry
            Next i
            fact=Ltrim(c,"0")
      Next z
      Return fact
End Function


Var f= factorial(12)

Print f
Sleep

 

[srvaldez]

thank dodicat for the feedback
the bignum_divmod sub is giving wrong result, need to debug

[srvaldez]

the code at https://github.com/kokke/tiny-bignum-c compiles to a mere 13K in 64-bit so if anyone wants they can make a small lib
I will try and see where I went wrong with the translation to fb

[dodicat]

This seems to work

Code: Select all

private sub bignum_to_string(byref n as bn, byref st as zstring, byval nbytes as long)
	'assert(-(n andalso "n is null"))
	'assert(-(str andalso "str is null"))
	'assert(-((nbytes > 0) andalso "nbytes must be positive"))
	'assert(-(((nbytes and 1) = 0) andalso "string format must be in hex -> equal number of bytes"))
	dim j as long = BN_ARRAY_SIZE - 1
	dim i as long = 0
	while (j >= 0) andalso (nbytes > (i + 1))
		sprintf(@st[i], "%.08x", n.array(j))
		i += 2 * 4
		j -= 1
	wend
	j = 0
	while st[j] = asc("0")
		j += 1
	wend
	for i = 0 to (nbytes - j)-1
		st[i] = st[i + j]
	next
	st[i] = 0
end sub 

Which gives a hex string
factorial(12) using bignum = 1c8cfc00
which is 479001600
and

factorial(100) using bignum = 1b30964ec395dc24069528d54bbda40d16e966ef9a70eb21b5b2943a321cdf10391745570cca9420c6ecb3b72ed2ee8b02ea2735c61a000000000000000000000000
(actual from example)
1b30964ec395dc24069528d54bbda40d16e966ef9a70eb21b5b2943a321cdf10391745570cca9420c6ecb3b72ed2ee8b02ea2735c61a000000000000000000000000
NOTE:
(const BN_ARRAY_SIZE = 128 / WORD_SIZE) at the top

[srvaldez]

thanks dodicat
something is still wrong with the FB translation, but you can make a static lib of the C code easily enough
my aim was to limit the precision to 128-bits and hopefully have decent performance

[dodicat]

I just tested out my CHARACTERS THAT COUNT, part1 and part2.
Made in 2009
Only one tiny alteration, I had a statement between select case and case.
Just move the statement to above select case.
Tested win32latest. win64latest and also gas64.

print B("2","^","128")
sleep

answer
340282366920938463463374607431768211456
That's 2009 code running now.
I wonder what other compiler could do that, 1650 raw lines of code still valid (bar a tiny change) in an evolving new language after 13.5 years.

[srvaldez]

dodicat
I think that I got the code translated to FB ok, but it's inherently inefficient and terribly slow
and not only that, the parameter for the result in the functions are inconsistent, in some functions the result is the last parameter and in others the first
and you must take care that the destination is not among the operands
just in case that anyone is interested here's my latest translation

Code: Select all

#pragma once

#include once "crt/stdio.bi"
#include once "crt/stdint.bi"

extern "C"

#define __BIGNUM_H__
const WORD_SIZE = 4
const BN_ARRAY_SIZE = 128 \ WORD_SIZE
type DTYPE as ulong
type DTYPE_TMP as ulongint
#define DTYPE_MSB DTYPE_TMP(&h80000000)
#define SPRINTF_FORMAT_STR "%.08x"
#define SSCANF_FORMAT_STR "%8x"
#define MAX_VAL &hFFFFFFFFull
#define require(p, msg) assert(-(p andalso msg))

dim shared as boolean overflow

type bn
	array(0 to BN_ARRAY_SIZE - 1) as ulong
end type

enum
	SMALLER = -1
	EQUAL = 0
	LARGER = 1
end enum

declare sub bignum_init(byref n as bn)
declare sub bignum_from_int(byref n as bn, byval i as ulongint)
declare function bignum_to_int(byref n as bn) as long
declare sub bignum_from_string(byref n as bn, byval str as zstring ptr, byval nbytes as long)
declare sub bignum_to_string(byref n as bn, byval str as zstring ptr, byval maxsize as long)
declare sub bignum_add(byref a as bn, byref b as bn, byref c as bn)
declare sub bignum_sub(byref a as bn, byref b as bn, byref c as bn)
declare sub bignum_mul(byref a as bn, byref b as bn, byref c as bn)
declare sub bignum_div(byref a as bn, byref b as bn, byref c as bn)
declare sub bignum_mod(byref a as bn, byref b as bn, byref c as bn)
declare sub bignum_divmod(byref a as bn, byref b as bn, byref c as bn, byref d as bn)
declare sub bignum_and(byref a as bn, byref b as bn, byref c as bn)
declare sub bignum_or(byref a as bn, byref b as bn, byref c as bn)
declare sub bignum_xor(byref a as bn, byref b as bn, byref c as bn)
declare sub bignum_lshift(byref a as bn, byref b as bn, byval nbits as long)
declare sub bignum_rshift(byref a as bn, byref b as bn, byval nbits as long)
declare function bignum_cmp(byref a as bn, byref b as bn) as long
declare function bignum_is_zero(byref n as bn) as long
declare sub bignum_inc(byref n as bn)
declare sub bignum_dec(byref n as bn)
declare sub bignum_pow(byref a as bn, byref b as bn, byref c as bn)
declare sub bignum_isqrt(byref a as bn, byref b as bn)
declare sub bignum_assign(byref dst as bn, byref src as bn)
declare sub _lshift_one_bit(byref a as bn)
declare sub _rshift_one_bit(byref a as bn)
declare sub _lshift_word(byref a as bn, byval nwords as long)
declare sub _rshift_word(byref a as bn, byval nwords as long)

private sub bignum_init(byref n as bn)
	assert(-(n andalso "n is null"))
	dim i as long
	for i = 0 to BN_ARRAY_SIZE-1
		n.array(i) = 0
	next
end sub

private sub bignum_from_int(byref n as bn, byval i as ulongint)
	assert(-(n andalso "n is null"))
	bignum_init(n)
	n.array(0) = i
	dim num_32 as ulong = 32
	dim tmp as ulong = i shr num_32
	n.array(1) = tmp
end sub

private function bignum_to_int(byref n as bn) as long
	assert(-(n andalso "n is null"))
	dim ret as long = 0
	ret += n.array(0)
	return ret
end function

private sub bignum_from_string(byref n as bn, byval strng as zstring ptr, byval nbytes as long)
	assert(-(n andalso "n is null"))
	assert(-(strng andalso "str is null"))
	assert(-((nbytes > 0) andalso "nbytes must be positive"))
	assert(-(((nbytes and 1) = 0) andalso "string format must be in hex . equal number of bytes"))
	assert(-(((nbytes mod (sizeof(ulong) * 2)) = 0) andalso "string length must be a multiple of (sizeof(DTYPE) * 2) characters"))
	bignum_init(n)
	dim tmp as ulong
	dim i as long = nbytes - (2 * WORD_SIZE)
	dim j as long = 0
	while i >= 0
		tmp = 0
		sscanf(strng[i], "%8x", tmp)
		n.array(j) = tmp
		i -= 2 * WORD_SIZE
		j -= 1
	wend
end sub

private sub bignum_to_string(byref n as bn, byval strng as zstring ptr, byval nbytes as long)
	assert(-(n andalso "n is null"))
	assert(-(strng andalso "str is null"))
	assert(-((nbytes > 0) andalso "nbytes must be positive"))
	assert(-(((nbytes and 1) = 0) andalso "string format must be in hex . equal number of bytes"))
	dim j as long = BN_ARRAY_SIZE - 1
	dim i as long = 0
	while (j >= 0) andalso (nbytes > (i + 1))
		sprintf(strng[i], "%.08x", n.array(j))
		i += 2 * WORD_SIZE
		j -= 1
	wend
	j = 0
	while strng[j] = asc("0")
		j += 1
	wend
	i = 0
	while i < (nbytes - j)
		strng[i] = strng[(i + j)]
		i += 1
	wend
	strng[i] = 0
end sub

private sub bignum_dec(byref n as bn)
	assert(-(n andalso "n is null"))
	dim tmp as ulong
	dim res as ulong
	dim i as long
	For i = 0 To BN_ARRAY_SIZE - 1
		tmp = n.array(i)
		res = tmp - 1
		n.array(i) = res
		if not (res > tmp) then
			exit for
		end if
	next
end sub

private sub bignum_inc(byref n as bn)
	assert(-(n andalso "n is null"))
	dim res as ulong
	dim tmp as ulongint
	dim i as long
	For i = 0 To BN_ARRAY_SIZE - 1
		tmp = n.array(i)
		res = tmp + 1
		n.array(i) = res
		if res > tmp then
			exit for
		end if
	next
end sub

private sub bignum_add(byref a as bn, byref b as bn, byref c as bn)
	assert(-(a andalso "a is null"))
	assert(-(b andalso "b is null"))
	assert(-(c andalso "c is null"))
	dim tmp as ulongint
	dim carry as long = 0
	dim i as long
	For i = 0 To BN_ARRAY_SIZE - 1
		tmp = (culngint(a.array(i)) + b.array(i)) + carry
		carry = -(tmp > &hFFFFFFFFul)
		c.array(i) = tmp and &hFFFFFFFFul
	next
end sub

private sub bignum_sub(byref a as bn, byref b as bn, byref c as bn)
	assert(-(a andalso "a is null"))
	assert(-(b andalso "b is null"))
	assert(-(c andalso "c is null"))
	dim res as ulongint
	dim tmp1 as ulongint
	dim tmp2 as ulongint
	dim borrow as long = 0
	dim i as long
	For i = 0 To BN_ARRAY_SIZE - 1
		tmp1 = a.array(i) + (&hFFFFFFFFul + 1)
		tmp2 = b.array(i) + borrow
		res = tmp1 - tmp2
		c.array(i) = res and &hFFFFFFFFul
		borrow = -(res <= &hFFFFFFFFul)
	next
end sub

private sub bignum_mul(byref a as bn, byref b as bn, byref c as bn)
	assert(-(a andalso "a is null"))
	assert(-(b andalso "b is null"))
	assert(-(c andalso "c is null"))
	dim row as bn
	dim tmp as bn
	dim i as long
	dim j as long
	bignum_init(c)

	for i=0 to BN_ARRAY_SIZE-1
		bignum_init(row)
		for j=0 to BN_ARRAY_SIZE-1
			if (i + j) < BN_ARRAY_SIZE then
				bignum_init(tmp)
				dim intermediate as ulongint = a.array(i) * b.array(j)
				bignum_from_int(tmp, intermediate)
				_lshift_word(tmp, i + j)
				bignum_add(tmp, row, row)
			end if
		next
		bignum_add(c, row, c)
	next
end sub

private sub bignum_div(byref a as bn, byref b as bn, byref c as bn)
	assert(-(a andalso "a is null"))
	assert(-(b andalso "b is null"))
	assert(-(c andalso "c is null"))
	dim current as bn
	dim denom as bn
	dim tmp as bn
	bignum_from_int(current, 1)
	bignum_assign(denom, b)
	bignum_assign(tmp, a)
	dim half_max as const ulongint = 1 + &hFFFFFFFF \ 2
	overflow = false
	while bignum_cmp(denom, a) <> LARGER
		if denom.array((BN_ARRAY_SIZE - 1)) >= half_max then
			overflow = true
			exit while
		end if
		_lshift_one_bit(current)
		_lshift_one_bit(denom)
	wend
	if overflow = 0 then
		_rshift_one_bit(denom)
		_rshift_one_bit(current)
	end if
	bignum_init(c)
	while bignum_is_zero(current) = 0
		if bignum_cmp(tmp, denom) <> SMALLER then
			bignum_sub(tmp, denom, tmp)
			bignum_or(c, current, c)
		end if
		_rshift_one_bit(current)
		_rshift_one_bit(denom)
	wend
end sub

private sub bignum_lshift(byref a as bn, byref b as bn, byval nbits as long)
	assert(-(a andalso "a is null"))
	assert(-(b andalso "b is null"))
	assert(-((nbits >= 0) andalso "no negative shifts"))
	bignum_assign(b, a)
	dim nbits_pr_word as const long = WORD_SIZE * 8
	dim nwords as long = nbits \ nbits_pr_word
	if nwords <> 0 then
		_lshift_word(b, nwords)
		nbits -= nwords * nbits_pr_word
	end if
	if nbits <> 0 then
		dim i as long
		For i = (BN_ARRAY_SIZE - 1) To 1 Step -1
			b.array(i) = (b.array(i) shl nbits) or (b.array((i - 1)) shr ((8 * WORD_SIZE) - nbits))
		next
		b.array(i) shl= nbits
	end if
end sub

private sub bignum_rshift(byref a as bn, byref b as bn, byval nbits as long)
	assert(-(a andalso "a is null"))
	assert(-(b andalso "b is null"))
	assert(-((nbits >= 0) andalso "no negative shifts"))
	bignum_assign(b, a)
	dim nbits_pr_word as const long = WORD_SIZE * 8
	dim nwords as long = nbits \ nbits_pr_word
	if nwords <> 0 then
		_rshift_word(b, nwords)
		nbits -= nwords * nbits_pr_word
	end if
	if nbits <> 0 then
		dim i as long = 0
		while i < (BN_ARRAY_SIZE - 1)
			b.array(i) = (b.array(i) shr nbits) or (b.array((i + 1)) shl ((8 * WORD_SIZE) - nbits))
			i += 1
		wend
		b.array(i) shr= nbits
	end if
end sub

private sub bignum_mod(byref a as bn, byref b as bn, byref c as bn)
	assert(-(a andalso "a is null"))
	assert(-(b andalso "b is null"))
	assert(-(c andalso "c is null"))
	dim tmp as bn
	bignum_divmod(a, b, tmp, c)
end sub

private sub bignum_divmod(byref a as bn, byref b as bn, byref c as bn, byref d as bn)
	assert(-(a andalso "a is null"))
	assert(-(b andalso "b is null"))
	assert(-(c andalso "c is null"))
	dim tmp as bn
	bignum_div(a, b, c)
	bignum_mul(c, b, tmp)
	bignum_sub(a, tmp, d)
end sub

private sub bignum_and(byref a as bn, byref b as bn, byref c as bn)
	assert(-(a andalso "a is null"))
	assert(-(b andalso "b is null"))
	assert(-(c andalso "c is null"))
	dim i as long
	For i = 0 To BN_ARRAY_SIZE - 1
		c.array(i) = a.array(i) and b.array(i)
	next
end sub

private sub bignum_or(byref a as bn, byref b as bn, byref c as bn)
	assert(-(a andalso "a is null"))
	assert(-(b andalso "b is null"))
	assert(-(c andalso "c is null"))
	dim i as long = 0
	For i = 0 To BN_ARRAY_SIZE - 1
		c.array(i) = a.array(i) or b.array(i)
	next
end sub

private sub bignum_xor(byref a as bn, byref b as bn, byref c as bn)
	assert(-(a andalso "a is null"))
	assert(-(b andalso "b is null"))
	assert(-(c andalso "c is null"))
	dim i as long
	For i = 0 To BN_ARRAY_SIZE - 1
		c.array(i) = a.array(i) xor b.array(i)
	next
end sub

private function bignum_cmp(byref a as bn, byref b as bn) as long
	assert(-(a andalso "a is null"))
	assert(-(b andalso "b is null"))
	dim i as long = BN_ARRAY_SIZE
	do
		i -= 1
		if a.array(i) > b.array(i) then
			return LARGER
		elseif a.array(i) < b.array(i) then
			return SMALLER
		end if
	loop while i <> 0
	return EQUAL
end function

private function bignum_is_zero(byref n as bn) as long
	assert(-(n andalso "n is null"))
	dim i as long
	For i = 0 To BN_ARRAY_SIZE - 1
		if n.array(i) then
			return 0
		end if
	next
	return 1
end function

private sub bignum_pow(byref a as bn, byref b as bn, byref c as bn)
	assert(-(a andalso "a is null"))
	assert(-(b andalso "b is null"))
	assert(-(c andalso "c is null"))
	dim tmp as bn
	bignum_init(c)
	if bignum_cmp(b, c) = EQUAL then
		bignum_inc(c)
	else
		dim bcopy as bn
		bignum_assign(bcopy, b)
		bignum_assign(tmp, a)
		bignum_dec(bcopy)
		while bignum_is_zero(bcopy) = 0
			bignum_mul(tmp, a, c)
			bignum_dec(bcopy)
			bignum_assign(tmp, c)
		wend
		bignum_assign(c, tmp)
	end if
end sub

private sub bignum_isqrt(byref a as bn, byref b as bn)
	assert(-(a andalso "a is null"))
	assert(-(b andalso "b is null"))
	dim low as bn
	dim high as bn
	dim midle as bn
	dim tmp as bn
	bignum_init(low)
	bignum_assign(high, a)
	bignum_rshift(high, midle, 1)
	bignum_inc(midle)
	while bignum_cmp(high, low) > 0
		bignum_mul(midle, midle, tmp)
		if bignum_cmp(tmp, a) > 0 then
			bignum_assign(high, midle)
			bignum_dec(high)
		else
			bignum_assign(low, midle)
		end if
		bignum_sub(high, low, midle)
		_rshift_one_bit(midle)
		bignum_add(low, midle, midle)
		bignum_inc(midle)
	wend
	bignum_assign(b, low)
end sub

private sub bignum_assign(byref dst as bn, byref src as bn)
	assert(-(dst andalso "dst is null"))
	assert(-(src andalso "src is null"))
	dim i as long
	For i = 0 To BN_ARRAY_SIZE - 1
		dst.array(i) = src.array(i)
	next
end sub

private sub _rshift_word(byref a as bn, byval nwords as long)
	assert(-(a andalso "a is null"))
	assert(-((nwords >= 0) andalso "no negative shifts"))
	dim i as long
	if nwords >= BN_ARRAY_SIZE then
		For i = 0 To BN_ARRAY_SIZE - 1
			a.array(i) = 0
		next
		return 'exit sub
	end if
	i = 0
	while i < (BN_ARRAY_SIZE - nwords)
		a.array(i) = a.array((i + nwords))
		i += 1
	wend
	while i < BN_ARRAY_SIZE
		a.array(i) = 0
		i += 1
	wend
end sub

private sub _lshift_word(byref a as bn, byval nwords as long)
	assert(-(a andalso "a is null"))
	assert(-((nwords >= 0) andalso "no negative shifts"))
	dim i as long
	For i = (BN_ARRAY_SIZE - 1) To nwords Step -1
		a.array(i) = a.array((i - nwords))
	next
	while i >= 0
		a.array(i) = 0
		i -= 1
	wend
end sub

private sub _lshift_one_bit(byref a as bn)
	assert(-(a andalso "a is null"))
	dim i as long
	For i = (BN_ARRAY_SIZE - 1) To 1 Step -1
		a.array(i) = (a.array(i) shl 1) or (a.array((i - 1)) shr ((8 * WORD_SIZE) - 1))
	next
	a.array(0) shl= 1
end sub

private sub _rshift_one_bit(byref a as bn)
	assert(-(a andalso "a is null"))
	dim i as long = 0
	while i < (BN_ARRAY_SIZE - 1)
		a.array(i) = (a.array(i) shr 1) or (a.array((i + 1)) shl ((8 * WORD_SIZE) - 1))
		i += 1
	wend
	a.array((BN_ARRAY_SIZE - 1)) shr= 1
end sub

private sub factorial(byref n as bn, byref res as bn)
	dim tmp as bn
	bignum_assign(tmp, n)
	bignum_dec(n)
	while bignum_is_zero(n) = 0
		bignum_mul(tmp, n, res)
		bignum_dec(n)
		bignum_assign(tmp, res)
	wend
	bignum_assign(res, tmp)
end sub

private sub bignum_to_hex_string(byref n as bn, byref st as string)
	'assert(-(n andalso "n is null"))
	'assert(-(str andalso "str is null"))
	'assert(-((nbytes > 0) andalso "nbytes must be positive"))
	'assert(-(((nbytes and 1) = 0) andalso "string format must be in hex -> equal number of bytes"))
	dim as string dgts
	st=""
	for j as long=BN_ARRAY_SIZE - 1 to 0 step -1
		dgts=trim(hex(n.array(j)))
		if len(dgts)<8 then dgts=string(8-len(dgts), "0")+dgts
		st+=dgts
	next
	st=ltrim(st, "0")
end sub

end extern

sub valbn(byref w as bn, byref strn as string)
	dim as bn one, rm, quo, ten, bt
	dim as string digits, s=strn
	dim as long ln
	s=trim(s)
	s=ltrim(s, "0")
	ln=len(s)
	if ln=0 then
		bignum_init(w)
		goto finished
	end if
	if ln<10 then
		w.array(0)=CuLng(s)
		goto finished
	end if
	if ln>38 then
		s=left(s, 38)
	end if
	bignum_from_int(bt, 1000000000)
	
	digits=left(s, 9)
	s=mid(s, 10)
	ln=len(s)
	w.array(0)=CuLng(digits)
	bignum_init(rm)

	while ln>9
		digits=left(s, 9)
		s=mid(s, 10)
		ln=len(s)
		bignum_mul(bt, w, one)
		w=one
		rm.array(0)=CuLng(digits)
		bignum_add(w, rm, w)
	wend

	if ln>0 then
		bt.array(0)=CLng("1"+string(ln, "0"))
		bignum_mul(bt, w, one)
		w=one
		rm.array(0)=CLng(s)
		bignum_add(rm, w, w)
	end if

finished:
end sub

function strbn(byref w as bn) as string
	dim as bn quo, rm, ten, tmp
	dim as string digits, s
	dim as long i
	s=""
	bignum_from_int(ten, 1000000000)
	bignum_divmod(w, ten, quo, rm)
	digits=trim(str(rm.array(0)))
	if len(digits)<9 then
		digits=string(9-len(digits), "0")+digits
	end if
	s=digits+s
	
	for i=1 to BN_ARRAY_SIZE*1.08
		tmp=quo
		bignum_divmod(tmp, ten, quo, rm)
		digits=trim(str(rm.array(0)))
		if len(digits)<9 then
			digits=string(9-len(digits), "0")+digits
		end if
		s=digits+s
	next
	tmp=quo
	bignum_divmod(tmp, ten, quo, rm)
	digits=trim(str(rm.array(0)))  : s=digits+s
	s=ltrim(s, "0")
	if s="" then s="0"

	return s
end function

dim as bn num, den, q, r, result, tmp, m
dim as string s
dim as long j
dim as double t

valbn(num, "999999999999999999998888888888888888")
valbn(den, "18446744073709551616")
? "numerator     = ";strbn(num)
bignum_to_hex_string(num, s)
? "hex numerator = ";s
?
? "denominator     = ";strbn(den)
bignum_to_hex_string(den, s)
? "hex denominator = ";s
?
bignum_divmod(num, den, q, r)
? "quotient  = ";strbn(q)
? "remainder = ";strbn(r)
sleep

output

Code: Select all

numerator     = 999999999999999999998888888888888888
hex numerator = C097CE7BC90715B347AC8348EA8E38

denominator     = 18446744073709551616
hex denominator = 10000000000000000

quotient  = 54210108624275221
remainder = 12918483735999581752

I think that it would be nice to have a 128-bit integer type but the code presented is simply inadequate

[deltarho[1859]]

I am not interested in 128-bit division. However, I see that we are talking 34 significant decimal digits. That is in the Planck unit domain

[srvaldez]

hello deltarho[1859]
for a complete integer library one must include division with remainder, add, subtract and multiply are simple enough but division is more complex
there's an efficient 256-bit library at https://github.com/piggypiggy/fp256/tree/master/src with Apache 2 license but it uses asm and is for x64 only

[deltarho[1859]]

division is more complex

and why gcc replaces 1/2^32 with 2.328306436538696e-010 - much faster. With gas and gas64 we have to do it.

[SARG]

With gas and gas64 we have to do it.

With gas64 it's ok. The compiler provides directly the value.

Code: Select all

dim as double aa=1/2^32 

Code: Select all

# store AA.3+-72 [double] := 2.328306436538696e-010 [double]
# v1=var AA ofs=-72 [double] symbdump=var local accessed declared AA [double]
# v2=imm 2.328306436538696e-010 [double] symbdump=<NULL>
mov rax, 0x3DF0000000000000 # DBL=2.328306436538696e-010
mov QWORD PTR -72[rbp], rax

[deltarho[1859]]

Thanks, SARG.