danbaron
25-09-2011, 07:24
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
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
timestring2 = "elapsed time = " + timestring1 + " seconds"
Print timestring2
WaitKey$
End Function