Task

Explicitly implement   long multiplication.

This is one possible approach to arbitrary-precision integer algebra.



For output, display the result of    264 * 264.

Optionally, verify your result against builtin arbitrary precision support.

The decimal representation of    264    is:

18,446,744,073,709,551,616

The output of    264 * 264    is    2128,    and is:

340,282,366,920,938,463,463,374,607,431,768,211,456



 
'[RC] long multiplication
 
'now, count 2^64
print "2^64"
a$="1"
for i = 1 to 64
    a$ = multByD$(a$, 2)
next
print a$
print "(check with native LB)"
print 2^64
print "(looks OK)"
 
'now let's do b$*a$ stuff
print
print "2^64*2^64"
print longMult$(a$, a$)
print "(check with native LB)"
print 2^64*2^64
print "(looks OK)"
 
end
'---------------------------------------
function longMult$(a$, b$)
    signA = 1
    if left$(a$,1) = "-" then a$ = mid$(a$,2): signA = -1
    signB = 1
    if left$(b$,1) = "-" then b$ = mid$(b$,2): signB = -1
 
    c$ = ""
    t$ = ""
    shift$ = ""
    for i = len(a$) to 1 step -1
        d = val(mid$(a$,i,1))
        t$ = multByD$(b$, d)
        c$ = addLong$(c$, t$+shift$)
        shift$ = shift$ +"0"
    'print d, t$, c$ 
    next
    if signA*signB<0 then c$ = "-" + c$
    'print c$
    longMult$ = c$
end function
 
function multByD$(a$, d)
'multiply a$ by digit d
c$ = ""
carry = 0
for i = len(a$) to 1 step -1
        a = val(mid$(a$,i,1))
        c = a*d+carry
        carry = int(c/10)
        c = c mod 10
        'print a, c
        c$ = str$(c)+c$ 
next
    if carry>0 then c$ = str$(carry)+c$
    'print c$
    multByD$ = c$
end function
 
function addLong$(a$, b$)
'add a$ + b$, for now only positive
    l = max(len(a$), len(b$))
    a$=pad$(a$,l)
    b$=pad$(b$,l)
    c$ = "" 'result
    carry = 0
    for i = l to 1 step -1
        a = val(mid$(a$,i,1))
        b = val(mid$(b$,i,1))
        c = a+b+carry
        carry = int(c/10)
        c = c mod 10
        'print a, b, c
        c$ = str$(c)+c$
    next
    if carry>0 then c$ = str$(carry)+c$
    'print c$
    addLong$ = c$
end function
 
function pad$(a$,n)  'pad from right with 0 to length n
     pad$ = a$
     while len(pad$)<n
        pad$ = "0"+pad$
     wend
end function
 
 
 