Over the summer, I had fantastical ideas for creating an arbitrary precision math app. It didn't get far at all and that project pretty much stopped. However, one of the routines I rather like was the Arbitrary Precision Multiplication routine. In the project, I had it read Str1 and Str2, convert the numbers to hex, then I used the routine to multiply them and then it converted it back to decimal for output. It was able to handle numbers several hundred digits long (I think two 3048 bit numbers, could be stored in saveSScreen with the output in AppBackUpScreen, so both would be 918 digits, producing an 1845 digit number).
Anyways, I figured I would share it in case anybody else wanted to use it
Code:
As a warning, using huge numbers can actually take quite a while. I tried multiplying two very large numbers, and with the time it took to convert the numbers, multiply, then convert back, I think I got it to take almost an hour to compute. Then again, they were almost a thousand digits long XD
For anybody that wants to see it in Action, BatLib uses this routine for its base conversions. This is why it can convert numbers in one base to another that are hundreds of digits long.
Anyways, I figured I would share it in case anybody else wanted to use it
Code:
;===============================================================
AP_Mul_AP:
;===============================================================
;Inputs:
; HL points to the first number (little-endian, size prefix 2 bytes)
; DE points to the second number (little-endian, size prefix 2 bytes)
; BC points to the output location
;Output:
; The RAM at HL contains the product (little-endian with
; size prefix). Size is adjusted so there won't be zeroes
; at the end.
;Notes:
; This will erase bytes of RAM at (HL) equal to the
; size of the first number plus the size of the second.
; So if you use saveSScreen:
; First number uses 2+M bytes
; Second number uses 2+N bytes
; Output number uses 2+M+N bytes
; At most, 2+N+2+M+2+M+N=768.
; 2+N+2+M+2+M+N = 768
; 6+2M+2N = 768
; 2(M+N) = 762
; M+N = 381
; In otherwords, you can multiply two, 190 byte numbers. In
; Decimal, this comes out to roughly two 457 digit numbers
; to get up to 915 digit number. It requires 14952 bytes of
; RAM to use two numbers >9000 digits
;===============================================================
di
;First, we get the size
ld (output),bc ;4 bytes, save the output location
ld c,(hl)
inc hl
ld b,(hl)
inc hl
ld (Num1Loc),hl ;3 bytes, save the location of the first number
ld (Num1Size),bc ;4 bytes, save the size
ex de,hl
ld e,(hl)
inc hl
ld d,(hl)
add hl,de
ld (Num2Loc),hl ;3 bytes, save the location
ld (Num2Size),de ;4 bytes, save the size
ex de,hl
add hl,bc ;size of the output RAM
;Now we clear out the bytes for the output
ld b,h
ld c,l
ld hl,(output)
ld (hl),c
inc hl
ld (hl),b
inc hl
ld (output),hl
ld (Num3Size),bc
xor a
ld (hl),a
cpi
jp pe,$-3
;Now we start multiplying stuff
;We need to do:
; hl=(Num2Loc)
; de=(Num1Loc)
; ix=(output)
; bc=(Num2Size)
;(hl)_Times_(de)_To_(ix)
exx
ld bc,(Num3Size)
exx
ld bc,(Num2Size)
; ld hl,(Num2Loc)
ex de,hl
Loop1:
push bc
ld b,8
Loop2:
;===============================================================
; rl (output)
;===============================================================
exx
ld hl,(output)
ld d,b
ld e,c
dec de
inc d
inc e
or a
rl (hl)
inc hl
dec e
jr nz,$-4
dec d
jr nz,$-7
exx
;===============================================================
rlc (hl)
jr nc,NoAdd
;add (output),(Num1Loc)
exx
ld de,(Num1Loc)
push bc
ld bc,(Num1Size)
dec bc
inc c
inc b
ld hl,(output)
or a
AddLoop:
ld a,(de)
adc a,(hl)
ld (hl),a
inc hl
inc de
dec c
jr nz,AddLoop
dec b
jr nz,AddLoop
jr nc,$+3
inc (hl)
pop bc
exx
NoAdd:
djnz Loop2
pop bc
cpd
jp pe,Loop1
ld hl,(output)
ld bc,(Num3Size)
add hl,bc
dec hl
inc bc
xor a
cpd
jp po,$+5
jr z,$-5
ld hl,(output)
dec hl
ld (hl),b
dec hl
ld (hl),c
ret
As a warning, using huge numbers can actually take quite a while. I tried multiplying two very large numbers, and with the time it took to convert the numbers, multiply, then convert back, I think I got it to take almost an hour to compute. Then again, they were almost a thousand digits long XD
For anybody that wants to see it in Action, BatLib uses this routine for its base conversions. This is why it can convert numbers in one base to another that are hundreds of digits long.