C to PBCC6

[danbaron]

I'm trying to do fast multiplication for big integers.

I started out by doing it in C.

But, I found C frustrating in a lot of ways.

When the program got big enough so that I needed to break it into separate files, and then I had to deal with header files, I broke down and decided to try translating it into PowerBasic.

As usual with any language that you seldom use, at first I couldn't figure out how to do many things.

But, after a while, it wasn't so bad.

So far, I got simple (pencil and paper) multiplication to work.

It turns out that even for fast multiplication (Toom-3, I don't know about Schonhage (FFT)) of big integers, you still need routines that do simple multiplication.

The program below uses PBCC6 to multiply two 5000 digit integers (I did this previously in C), 1565^1565 and 1564^1566.

It doesn't run as fast as C, but, it was a lot easier to program.

And, it seems that when the program is divided into multiple files, everything will be simpler.

#Compile Exe
#Dim All

'------------------------------------------------------------------------------------------------------

%true = -1
%false = 0
%pos = -1
%neg = 0
%base10 = 10
%maxdigits = 12000

Type reg
ndigits As Long
address As Long
d As Byte Ptr
maxpower As Integer
sign As Integer
End Type

'------------------------------------------------------------------------------------------------------

Sub setregdigits(ByRef r As reg, nd As Long)
r.ndigits = nd
GlobalMem Alloc nd To r.address
GlobalMem Lock r.address To r.d
Memory Fill r.d, nd, Byte 0
End Sub

'------------------------------------------------------------------------------------------------------

Sub zeroreg(ByRef r As reg)
Local i As Long

For i = 0 To r.ndigits - 1
r.@d[i] = 0
Next
End Sub

'------------------------------------------------------------------------------------------------------

Function maxregpower(ByRef r As reg) As Integer
Dim i As Local Integer

For i = r.ndigits To -1 Step -1
If r.@d[i] > 0 Then Exit For
Next
Function = i
End Function

'------------------------------------------------------------------------------------------------------

Function comparemags(ByRef r1 As reg, ByRef r2 As reg) As Integer
' returns %true if abs(r1) >= abs(r2)
' else returns %false
Local i As Integer
Local p1 As Integer
Local p2 As Integer

p1 = r1.maxpower
p2 = r2.maxpower

If p1>p2 Then
Function = %true
Exit Function
End If

If p1<p2 Then
Function = %false
Exit Function
End If

For i = p1 To 0 Step -1
If r1.@d[i]<r2.@d[i] Then
Function = %false
Exit Function
End If

If r1.@d[i]>r2.@d[i] Then
Function = %true
Exit Function
End If
Next

Function = %true
End Function

'------------------------------------------------------------------------------------------------------

Sub setregsequal(ByRef r1 As reg, ByRef r2 As reg)
' r1 = r2
Dim i As Local Long
r1.sign = r2.sign
r1.maxpower = r2.maxpower
For i = 0 To r2.maxpower
r1.@d[i] = r2.@d[i]
Next
End Sub

'------------------------------------------------------------------------------------------------------

Function regiszero(ByRef r As reg) As Integer
If r.maxpower = -1 Then
Function = %true
Exit Function
Else
Function = %false
Exit Function
End If
End Function

'------------------------------------------------------------------------------------------------------

Sub reversecopystringtoreg(ByRef s As String, ByRef r As reg)
Local sl As Long
Local i As Long
Local j As Long

sl = Len(s)
j = 0
r.sign = %pos
If Mid$(s,1,1)= "+" Then j=1
If Mid$(s,1,1)= "-" Then
j=1
r.sign = %neg
End If
r.maxpower = sl - 1 - j
For i = 0 To r.maxpower
r.@d[i] = Val(Mid$(s, sl - i, 1))
Next
End Sub

'------------------------------------------------------------------------------------------------------

Sub reversecopyregtostring(ByRef r As reg, ByRef s As String)
Local i As Long
Local j As Long
Local mp As Integer
mp = r.maxpower

If mp = -1 Then
s = "0"
Exit Sub
End If

j = 0
If r.sign = %neg Then
j = 1
Mid$(s,1,1) = "-"
End If
s = Repeat$(mp + j + 1, "0")
For i = 0 To r.maxpower
Mid$(s, r.maxpower + 1 + j - i, 1) = Chr$(r.@d[i] + 48)
Next
End Sub

'------------------------------------------------------------------------------------------------------

Sub add(ByRef r1 As reg, ByRef r2 As reg, ByRef r3 As reg)
' r1 + r2 = r3
Local sum As Word
Local i As Long
Local j As Long
Local mp1 As Integer
Local mp2 As Integer
Local mp As Integer
Local carry As Byte

carry = 0
mp1 = r1.maxpower
mp2 = r2.maxpower

mp = mp1
If mp2>mp Then mp = mp2
j = 0
For i = 0 To mp
sum = r1.@d[i] + r2.@d[i] + carry
carry = sum \ %base10
r3.@d[i] = sum Mod %base10
Next

If carry > 0 Then
r3.@d[mp + 1] = carry
j = 1
End If
r3.maxpower = mp + j
End Sub

'------------------------------------------------------------------------------------------------------

Sub subt(ByRef r1 As reg, ByRef r2 As reg, ByRef r3 As reg)
' r1 - r2 = r3
Local subb As Integer
Local i As Long
Local j As Long
Local mp1 As Integer
Local mp2 As Integer
Local mp As Integer
Local borrow As Byte

borrow = 0
mp1 = r1.maxpower
mp2 = r2.maxpower

mp = mp1
If mp2>mp Then mp = mp2
j = 0

For i = 0 To mp
subb = r1.@d[i] - r2.@d[i] - borrow
If subb < 0 Then
subb += %base10
borrow = 1
Else
borrow = 0
r3.@d[i] = subb
End If
Next
r3.maxpower = maxregpower(r3)
End Sub

'------------------------------------------------------------------------------------------------------

Sub regadd(ByRef r1 As reg, ByRef r2 As reg, ByRef r3 As reg)
' r1 + r2 = r3
Static countt As Long
Local s1 As Integer
Local s2 As Integer
Static temp As reg

If countt = 0 Then
setregdigits(temp,  %maxdigits)
countt += 1
End If

temp.sign = %pos

s1 = r1.sign
s2 = r2.sign

If(s1 And s2) Then
add(r1,r2,temp)
temp.sign=%pos
End If

If(Not s1 And Not s2) Then
add(r1,r2,temp)
temp.sign=%neg
End If

If(Not s1 And s2) Then
If comparemags(r2,r1) Then
subt(r2,r1,temp)
temp.sign = %pos
Else
subt(r1,r2,temp)
If Not regiszero(temp) Then
temp.sign = %neg
End If
End If
End If

If(s1 And Not s2) Then
If comparemags(r1,r2) Then
subt(r1,r2,temp)
temp.sign = %pos
Else
subt(r2,r1,temp)
If Not regiszero(temp) Then
temp.sign = %neg
End If
End If
End If

setregsequal(r3,temp)
End Sub

'------------------------------------------------------------------------------------------------------

Sub regsub(ByRef r1 As reg, ByRef r2 As reg, ByRef r3 As reg)
' r1 + r2 = r3
Static countt As Byte
Local s1 As Integer
Local s2 As Integer
Static temp As reg

If countt = 0 Then
setregdigits(temp,  %maxdigits)
countt += 1
End If

temp.sign = %pos

s1 = r1.sign
s2 = r2.sign

If( s1 And s2) Then
If comparemags(r1,r2) Then
subt(r1,r2,temp)
temp.sign = %pos
Else
subt(r2,r1,temp)
If Not regiszero(temp) Then
temp.sign = %neg
End If
End If
End If

If( Not s1 And Not s2) Then
If comparemags(r1,r2) Then
subt(r1,r2,temp)
If Not regiszero(temp) Then
temp.sign = %neg
End If
Else
subt(r2,r1,temp)
temp.sign = %pos
End If
End If

If(Not s1 And s2) Then
add(r1,r2,temp)
If Not regiszero(temp) Then
temp.sign = %neg
End If
End If

If(s1 And Not s2) Then
add(r1,r2,temp)
temp.sign=%pos
End If

setregsequal(r3,temp)
End Sub

'------------------------------------------------------------------------------------------------------

Sub multregbydigit(ByRef r1 As reg, ByRef r2 As reg, digit As Byte, shft As Long)
' r2 = r1 * digit
Static countt As Byte
Local mp As Integer
Local product As Word
Local i As Long
Local j As Long
Static temp As reg
Local carry As Byte

carry = 0
j = 0

If countt = 0 Then
setregdigits(temp,  %maxdigits)
countt += 1
End If

mp = r1.maxpower

For i = 0 To mp
product = r1.@d[i] * digit + carry
carry = product \ %base10
 temp.@d[i + shft] = product Mod %base10
Next

For i = 0 To shft - 1
temp.@d[i] = 0
Next

If carry > 0 Then
j = 1
temp.@d[mp + j + shft] = carry
End If

temp.sign = r1.sign
temp.maxpower = mp + j + shft
setregsequal(r2, temp)
End Sub

'------------------------------------------------------------------------------------------------------

Sub divideregbydigit(ByRef r1 As reg, ByRef r2 As reg, digit As Byte, ByRef remain As Long)
' r2 = r1 * digit
Static countt As Byte
Local mp As Integer
Local d As Byte
Local q As Byte
Local r As Byte
Local i As Long
Local j As Long
Static temp As reg

j = -1

If countt = 0 Then
setregdigits(temp,  %maxdigits)
countt += 1
End If

mp = r1.maxpower

For i = mp To 0 Step -1
d = %base10 * r + r1.@d[i]
q = d \ digit
If i=mp And q>0 Then j=0
temp.@d[i] = q
r = d Mod digit
Next

temp.sign = r1.sign
temp.maxpower = mp + j
setregsequal(r2, temp)
remain = r
End Sub

'------------------------------------------------------------------------------------------------------

Sub regmult(ByRef r1 As reg, ByRef r2 As reg, ByRef r3 As reg)
' r3 = r1 * r2
Static temp1 As reg
Static temp2 As reg
Static countt As Byte
Local i As Long
Local mp1 As Integer
Local mp2 As Integer
Local hold As Integer

hold = r2.sign
r2.sign = %pos

If countt = 0 Then
setregdigits(temp1, %maxdigits)
setregdigits(temp2, %maxdigits)
countt += 1
End If

mp1 = r1.maxpower
mp2 = r2.maxpower

For i = 0 To mp1
multregbydigit(r2, temp1, r1.@d[i], i)
regadd(temp1, temp2, temp2)
Next

r2.sign = hold

setregsequal(r3, temp2)

If (((r1.sign = %pos) And (r2.sign = %pos)) Or ((Not r1.sign = %pos) And (Not r2.sign = %pos))) Then
r3.sign = %pos
Else
r3.sign = %neg
End If
End Sub

'------------------------------------------------------------------------------------------------------

Function elapsedtime(t1 As Double) As Double
Local t2 As Double

t2 = Timer
If t1>t2 Then t2 += 86400
Function = t2 - t1
End Function

'------------------------------------------------------------------------------------------------------

Function PBMain () As Long
Local s1 As String
Local s2 As String
Local s3 As String
Local num1 As reg
Local num2 As reg
Local num3 As reg
Local t1 As Double
Local tt As Double
Local timestring1 As String
Local timestring2 As String

' s1 = 1565^1565

s1 = _
  "25998305698778882782694282216427520062325059925056858892956364318072249183875081" _
+ "68442463096175264507182962040625952405271506061048605031872834827638275762132253" _
+ "73858445634105522970396018248984984361543008819047090626470992519569266493011239" _
+ "81385713161641125513067028830936811472923500257024862707991584798971140541617300" _
+ "71234231202135809223242312655616315542948583438071887907514024590102337732384078" _
+ "73247871862406989702271177063193217340225057994600159267813767262212104205783683" _
+ "63025095177920225074834669646252545408427449351069515060097278605753619956900553" _
+ "86795407681744802443535225584885995769092731030367772359645778787948035071575082" _
+ "53503289863240458955982431760859690441697916187389932839106208311038104759463304" _
+ "92038066942096086838928671505951410997562150419005828041119390620070926224749330" _
+ "44811876158602334452145258026429850607093412457930099562830313117366885751915651" _
+ "35310474958330215531787533896617511151902175564933090237349475682507288214834576" _
+ "20981592706390501627359956921483881745921979876592412959264226532610844965533056" _
+ "03823828082715947774513221424937375043663476412308396807105569420007984249340080" _
+ "70124226805424103934896265174680289673701126520929835659871748979564184979293730" _
+ "45550019576989200303483284173094578415208174108966111657697671143910071201004209" _
+ "15169233837546621367856373302160998891694535450327805786016482732217698026063614" _
+ "40603263939359332375698364136585280539910291370562457066811608026783236764726683" _
+ "13253191452669007945741569955632534423125360266525673445710344893225336318036227" _
+ "51899802490385922414156963217848785122664633235788479138790465438621496053154871" _
+ "73265449103449852542128801432673156268199636851603649366783456131703429831019395" _
+ "58616468939108822708875327843669816436591423630016096816579847927321181094384808" _
+ "48971144589031804610332975513162952739089719888839081179410446068318437603084717" _
+ "68065017203019228437269987546251968940949710370152901914623079970495510312155857" _
+ "10531628560328469630530230738955807702048465618031979365349815954488779169464043" _
+ "80983107076650841323914686794178090751465245823400769670464670326638076080844984" _
+ "86090543541686857510467272349459625744971256146278089920197008015202026901138208" _
+ "25817340003057701196678502919432716213170216770030043873909619982612504305878265" _
+ "63384117053916125512691009340648815240201490510784486550498597569457045276884804" _
+ "91865119934397485463815538073854196931715904770807149099466503028609184021441221" _
+ "59089675228893305861570418194732610445826552339848389548697585828630934265012947" _
+ "51819363488772591396849482145412316967315364801141150691652872346064364671557159" _
+ "57870568873819933917795169659740301812765066254701635819988078720330945566076017" _
+ "12466383911567471431945132028284492008888627473183080652614885161771855164380212" _
+ "56512978748066431943525241224310973011888837173654921579048402850423671702268989" _
+ "49476674471179823846251058464063708473349960106833310306786814275642736388131948" _
+ "78853304014653428237678819866297610838549351485990743483386487071371788942431356" _
+ "45129870888909362061936491534282424966231253781963484583313517427756831015160329" _
+ "08460421876455141368075149317323870087337557877266063706878152841099564845544576" _
+ "02584912275268492270010276806384202285220161843604109696931612250710695403166096" _
+ "12011524876010688857641908772551802101359360026299544825344854352115301284299126" _
+ "01871502787383611403333990220554059532815646775153885994405874220641555781568174" _
+ "59134199947346374100959559692603359039655243341220363085112018667091742696030637" _
+ "78755681701026350607067305932389961340795092328701602727982045965114355375309786" _
+ "44330218738767773351405955056229902373326329657681337365859884155874806028591436" _
+ "77242431693996079457476508502891472765537837945937191083770030828201762130870310" _
+ "22795161096202928541405933619254574989906246644841265211804433276386092566107158" _
+ "24199398366344967746652790939781016393178900620040351585430416904327025672216116" _
+ "83434360955191759751176141733345322786732343897113347147010081549975643292804851" _
+ "44171393681671875475203079259426309412509694297381930371443878319798964013436284" _
+ "65780117439778511809284751185576752596740554256973137622081957317901735882634841" _
+ "45264502282597981982093584294482163518729558095112079267612165583911076485738457" _
+ "06812494083903873366071851446397049289636785999680657649308477853651523475322335" _
+ "52576705584073135488835033287183224933798541691954594398983338870795422146462358" _
+ "64356921050476220943937551133229566137714685998165093616730709543866077509213332" _
+ "72538937423092381584439092507337482407136298806936136101125596769949786666162714" _
+ "84145287731493057723165366990353272203559326978429596689051304429723917210971987" _
+ "63646897153112540248997458505889304985958232516312646311735644831173300178649902" _
+ "79267177572324356566298423592454528203459564599092014966942998266943638616048878" _
+ "56263567748856093177664375222549588154447598478535276027080215208489307640259709" _
+ "39579660389428258923069620672692556578816868263589345214720402757856535244008389" _
+ "11635718199286310046144595079464600464592471156199566437490374949272866165344859" _
+ "2183668353072789614088833332061767578125"

' s2 = 1564^1566

s2 = _
  "14953694418600598137797892976168196776550567060529797819121509629371302803543047" _
+ "94710002638603025393680933185989310939798144173493199247445066312919945504557291" _
+ "02848421764068990124330762271496575404885974897792031554855268481467499436416495" _
+ "11392608554481780601574566856704157263525144658586044732065080325505893485998816" _
+ "78743369109149811460642052784089771422917444151379142346575709856301223916415587" _
+ "57994793525336676787152374526553521316997756026971178406162991176203118480489761" _
+ "09462211584619286017572521118826425916626749242899525811083683907649791133130877" _
+ "99497113241181620701537075570351402846171686111030032654516905132393906765656637" _
+ "33012726208550756475555063211874755346836583180749084808343847318150367326348285" _
+ "83955161044563383458645555932626699166856579663826468440468662529885861962097371" _
+ "57516637209718863572931976654319891599277473185165878816845974781435780684185989" _
+ "99995748738383137861925308297636682237514758155596269988917999368638114799054174" _
+ "13893041900104361436509702432248713612735393747797344670573215467158837124664943" _
+ "19409517311781689273687251234877290377169799657738630741703123034988695752326512" _
+ "82336303577333586561656435418693490278554357901509893623951807741697921558458657" _
+ "91329928242819582039416749235148627494709871544555020100933246544735166204758852" _
+ "69703536176341896090069366921600832763359675089171251343765236529648019050977560" _
+ "84431011387072336307415426137514586109286563840589904762466328772473636080476570" _
+ "47384574983494620596683006824606808105530161811411516026056795740040655622679905" _
+ "11501554768974342945150251740204021288516232964847966538602548113294088458630841" _
+ "35782921536214837268668224918407201653054777132438526115466039492575739192016933" _
+ "47019306877933275222402190674678219165949517721242004971360669326466380830023692" _
+ "97298086106870476844804360788671423944136093456527786040949331054778122595410580" _
+ "45057562948725986606763108344320697500466136527832774576454067138871969914952539" _
+ "04480717387783316687760934071339958158439443272184466595634268407150307110702224" _
+ "28378638897951493613952668829798897534422626059331428625251962276364326192471629" _
+ "48483815669265297033419502214095114217328465436045481752075057310608441377208656" _
+ "95818022430570333219854583320117700195969473115380643833520674709196440916318387" _
+ "31006949282939384122823495555863036697471659428660153375694767964884757961167679" _
+ "12124344002806080332544135494560981966326048397563767252730000595110109701624287" _
+ "05055270197622223021855658024687104335544437894416942568488400081542892678241039" _
+ "69873333154288205338600609778427520548124029962599378710087898257189245049850198" _
+ "90927788235251272998474212768045082439287089460080388852001455593433597194810757" _
+ "46213246805651350163563308100725764948311268234822501637453283225820881849606453" _
+ "26765351947431320080552660635908345350943800038500391095106185664258722771669689" _
+ "28818852764380126290598594219377802142476053906801748435875619461831465647121811" _
+ "80398636631054612837398607429841997514309800563753476098847162048024084206017584" _
+ "04838089035474738962736283217374264765883445306310888553952447712151286626105775" _
+ "54973952543853157493575398455081916020756387754825722911462995957383017698708383" _
+ "56972416663581441602358752124755273082470825663787963443855037305223514437085248" _
+ "00990938020370728826463261435832143242164647475858177937927378771113828405763664" _
+ "22256975036416019294016390081028557048256053855874001700881088654869896568443072" _
+ "56957096459406069983892667934860590594212642070900353528817840151443990767147707" _
+ "06583186958602234705999155280559159818075169130946134849669862352857408492655215" _
+ "37151743022271701048065298275558716456555486556513796894228130585907963279591693" _
+ "15312738553791550430513924177822412226416688870759025433918610150608637460791569" _
+ "62472868803002737181835764800517361362293272097864666618282807170950994325182586" _
+ "21128572753868778281980536257832076751843925553309895270833936621821349335887275" _
+ "03843287271421499880958129106541726815265795925097182446884331285888015088738822" _
+ "10610349460483941171935273403293012896725297262632231479350344860770189200228711" _
+ "72728074469452024653647468316858108378915003291073420749373148147881776565232308" _
+ "17258373413715026851695500849050425519496830075479205266480235549233094958290190" _
+ "25401100005319496204483758233683486263744594863701040383866434637755702150279868" _
+ "87983173680297564514867086636686849893527912763767483845548700371780754162110819" _
+ "32500451458152686939788972837260816169766577003587059851122359323070088850008363" _
+ "99426465107228727319624180933023301011752873268800744924757487842854839838673206" _
+ "50034526740142373977837632195111344739307611431952436625675447738258430221254589" _
+ "78133681384750675229291278008026778055767752406341814804900169513527988934532877" _
+ "48010286982821323882394493683782522592476759019044097905674341162086346615322644" _
+ "37633169790035015446526660783709640299285895702764613315509042135055117925041047" _
+ "68744474423032874320585594733842996027579206308099156305659536475366018471863849" _
+ "83369412460853285459268558255370547720355889151527396706833050932459930701518437" _
+ "9886050781984586886687451347845490289934336"

setregdigits(num1, %maxdigits)
setregdigits(num2, %maxdigits)
setregdigits(num3, %maxdigits)

reversecopystringtoreg(s1,num1)
reversecopystringtoreg(s2,num2)

t1 = Timer
regmult(num1,num2,num3)
tt = elapsedtime(t1)
timestring1 = Format$(tt, "000.000")
reversecopyregtostring(num3,s3)
Print s3
Print
timestring2 = "elapsed time = " + timestring1 + " seconds"
Print timestring2
WaitKey$

End Function