Entry
TSE: Math: Number: Integer: Multiply: How to possibly multiply very long integers?
Jan 23rd, 2004 06:17
Knud van Eeden,
----------------------------------------------------------------------
--- Knud van Eeden --- 23 January 2004 - 00:28 am --------------------
TSE: Math: Number: Integer: Multiply: How to possibly multiply very
long integers?
---
Method: store the integers in strings, and multiply this integers by
using the same method as you use when multiplying two numbers on paper
---
The method used here mimics exactly the way you yourself multiply 2
integer
numbers.
---
That is:
1. You write the two numbers (usually underneath, otherwise besides)
each other
2. You start from the right
3. You take the next digit at this position from the (shortest) number
4. You repeatedly take the next right most digit at this position
from the (longest) number
5. You multiply this digits
6. You possibly add to this the old carry
7. In the result you put the digit which is the rest of 10
8. The new carry becomes the multiple of 10
9. You repeat steps 3 to 7 for the remaining digits
10. When you arrive at the first digit, you put the product and carry
unchanged in the result
11. You multiply this result by 10
12. You add this result to a subresult
13. You repeat the steps from 3. to 11.
14. You supply the total subresult
---
---
e.g.
12345
6789 x
--------
111105
98760
86415
74070
----------
83810205
---
Note:
the multiplying by 10 at each new row,
you mimic by adding an extra zero on the right for
each new row:
12345
6789 x
--------
111105
987600
8641500
74070000
----------
83810205
---
Note:
'div' or here '/' you use to find the multiple of 10.
'mod' you use to find the rest of 10
---
---
Note:
The maximum length of this integers is currently limited
to the maximum length of the string, thus about 255 characters.
Or thus about 255 digits.
---
---
--- cut here ---------------------------------------------------------
FORWARD PROC Main()
FORWARD STRING PROC FNStringGetMathAddIntegerTwoS( STRING s1, STRING
s2 )
FORWARD STRING PROC FNStringGetMathMultiplyIntegerTwoS( STRING s1,
STRING s2 )
// --- MAIN --- //
PROC Main()
Warn( FNStringGetMathMultiplyIntegerTwoS( "90", "10" ) ) //
gives "900"
Warn( FNStringGetMathMultiplyIntegerTwoS
( "3135814134123999", "513123413134123412341412342" ) ) //
gives "1609059651455932224225729024572564616995658"
Warn( FNStringGetMathMultiplyIntegerTwoS
( "12341234123413413241", "99897123412341234123412341341234" ) ) //
gives "1232853788287226631440261349156660317741059834879394"
END
<F12> Main()
// --- LIBRARY --- //
// library: string: get: math: multiply: integer: two
(filenamemacro=getstitx.s) [kn, ri, th, 22-01-2004 22:50:16]
STRING PROC FNStringGetMathMultiplyIntegerTwoS( STRING in1S, STRING
in2S )
// e.g. PROC Main()
// e.g. Warn( FNStringGetMathMultiplyIntegerTwoS( "90", "10" ) ) //
gives "900"
// e.g. Warn( FNStringGetMathMultiplyIntegerTwoS
( "3135814134123999", "513123413134123412341412342" ) ) //
gives "1609059651455932224225729024572564616995658"
// e.g. Warn( FNStringGetMathMultiplyIntegerTwoS
( "12341234123413413241", "99897123412341234123412341341234" ) ) //
gives "1232853788287226631440261349156660317741059834879394"
// e.g. END
// e.g.
// e.g. <F12> Main()
INTEGER restI = 0
INTEGER lengthminI = 0
INTEGER lengthmaxI = 0
INTEGER sumI = 0
INTEGER I = 0
INTEGER J = 0
INTEGER cminI = 0
STRING sumS[255] = ""
STRING minS[255] = ""
STRING maxS[255] = ""
STRING cminS[1] = ""
STRING cmaxS[1] = ""
STRING sumsubS[255] = ""
STRING zeroS[255] = ""
IF Length( in1S ) < Length( in2S )
minS = in1S
maxS = in2S
ELSE
minS = in2S
maxS = in1S
ENDIF
lengthminI = Length( minS )
lengthmaxI = Length( maxS )
FOR I = 1 TO lengthminI
cminS = minS[ lengthminI - I + 1 ]
cminI = Val( cminS )
sumsubS = ""
restI = 0
FOR J = 1 TO lengthmaxI
cmaxS = maxS[ lengthmaxI - J + 1 ]
sumI = ( Val( cmaxS ) * cminI ) + restI
IF sumI > 9 AND ( J <> lengthmaxI )
restI = sumI / ( 9 + 1 )
sumI = sumI MOD ( 9 + 1 )
ELSE
restI = 0
ENDIF
sumsubS = Str( sumI ) + sumsubS
ENDFOR
sumS = FNStringGetMathAddIntegerTwoS( sumS, sumsubS + zeroS )
zeroS = zeroS + "0"
ENDFOR
RETURN( sumS )
END
// library: string: get: math: add: integer: two
(filenamemacro=getstitw.s) [kn, ri, th, 22-01-2004 3:06:41]
STRING PROC FNStringGetMathAddIntegerTwoS( STRING in1S, STRING in2S )
// e.g. PROC Main()
// e.g. Warn( FNStringGetMathAddIntegerTwoS( "90", "1" ) ) //
gives "91"
// e.g. Warn( FNStringGetMathAddIntegerTwoS
( "3135814134123999", "513123413134123412341412342" ) ) //
gives "513123413137259226475536341"
// e.g. Warn( FNStringGetMathAddIntegerTwoS
( "12341234123413413241", "99897123412341234123412341341234" ) ) //
gives "99897123412353575357535754754475"
// e.g. END
// e.g.
// e.g. <F12> Main()
INTEGER restI = 0
INTEGER lengthminI = 0
INTEGER lengthmaxI = 0
INTEGER sumI = 0
INTEGER I = 0
INTEGER J = 0
STRING sumS[255] = ""
STRING minS[255] = ""
STRING maxS[255] = ""
STRING cminS[1] = ""
STRING cmaxS[1] = ""
IF Length( in1S ) < Length( in2S )
minS = in1S
maxS = in2S
ELSE
minS = in2S
maxS = in1S
ENDIF
lengthminI = Length( minS )
lengthmaxI = Length( maxS )
FOR I = 1 TO lengthmaxI
J = lengthminI - I + 1
IF J > 0
cminS = minS[ J ]
ELSE
cminS = "0"
ENDIF
cmaxS = maxS[ lengthmaxI - I + 1 ]
sumI = Val( cmaxS ) + Val( cminS ) + restI
IF sumI > 9 AND ( I <> lengthmaxI )
restI = sumI / ( 9 + 1 )
sumI = sumI MOD ( 9 + 1 )
ELSE
restI = 0
ENDIF
sumS = Str( sumI ) + sumS
ENDFOR
RETURN( sumS )
END
--- cut here ---------------------------------------------------------
---
---
Internet: see also:
---
TSE: Math: Number: Operation: Overview: Can you give an overview of
long digit operations in TSE?
http://www.faqts.com/knowledge_base/view.phtml/aid/28481/fid/1629
----------------------------------------------------------------------
