Results 1 to 1 of 1

Thread: C to PBCC6

  1. #1
    thinBasic MVPs danbaron's Avatar
    Join Date
    Jan 2010
    Location
    California
    Posts
    1,378
    Rep Power
    152

    C to PBCC6

    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
    
    Last edited by danbaron; 26-09-2011 at 00:30.
    "You can't cheat an honest man. Never give a sucker an even break, or smarten up a chump." - W.C.Fields

Members who have read this thread: 0

There are no members to list at the moment.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •