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



' version 08-01-2017
' compile with: fbc -s console
 
Const As UInteger base_ = 1000000000 ' base 1,000,000,000
 
Function multiply(a1 As String, b1 As String) As String
 
    Dim As String a = a1, b = b1
 
    Trim(a) : Trim(b) ' remove spaces 
    If Len(a) = 0 Or Len(b) = 0 Then Return "0"
 
    If Len(a) + Len(b) > 10000 Then 
        Print "number(s) are to big"
        Sleep 5000,1
        Return ""
    End If
 
    If Len(a) < Len(b) Then
        Swap a, b
    End If
 
    Dim As ULongInt product
    Dim As UInteger carry, i, m, shift
    Dim As UInteger la = Len(a), lb = Len(b)
    Dim As UInteger la9 = la \ 9 + IIf((la Mod 9) = 0, 0, 1)
    Dim As UInteger lb9 = lb \ 9 + IIf((lb Mod 9) = 0, 0, 1)
    Dim As UInteger arr_a(la9), answer((la9 + lb9) + 2)
    Dim As Integer last = la9
 
    ' make length a, b a multipy of 9
    a = Right((String(9, "0") + a), la9 * 9)
    b = Right((String(9, "0") + b), lb9 * 9)
 
    For i = 1 To la9
        arr_a(la9 - i +1) = Val(Mid(a, i * 9 -8, 9))
    Next
 
    Do
        carry = 0
        m = Val(Mid(b, lb9 * 9 -8, 9))
        For i = 1 To la9
            product = CULngInt(arr_a(i)) * m + answer(i + shift) + carry
            carry = product \ base_
            answer(i + shift) = product - carry * base_
        Next
        If carry <> 0 Then
            last = la9 + shift +1
            answer(last) = carry
        End If
        lb9 = lb9 -1
        shift = shift +1
    Loop Until lb9 = 0
 
    Dim As String tmp = Str(answer(last))
    last = last -1
    While last > 0
        tmp = tmp + Right(String(9,"0") + Str(answer(last)), 9)
        last = last -1
    Wend
 
    Return tmp
 
End Function
 
' ------=< MAIN >=------
 
Dim As String a = "2", b = "2", answer
Dim As UInteger i = 1, j
 
For j = 1 To 7
    answer = multiply(a, b)
    a = answer
    b = answer
    i = i + i
    Print using "2 ^ ### = "; i;
    Print answer
Next
 
Print
Print "-------------------------------------------------"
Print
 
a = "2" : b = "1" : answer = ""
For j = 1 To 128
    answer = multiply(a, b)
    b = answer
Next
Print "2 ^ 128 = "; answer
 
' empty keyboard buffer
While InKey <> "" : Wend
Print : Print "hit any key to end program"
Sleep
End