Generalised floating point multiplication: Difference between revisions
m (converted list to a table, removed Kudos.) |
m (→[[Generalised_floating_point_multiplication#ALGOL 68]]: removed # Kudos: use http://en.wikipedia.org/wiki/Karatsuba_algorithm #) |
||
Line 35: | Line 35: | ||
{{wont work with|ELLA ALGOL 68|Any (with appropriate job cards) - tested with release [http://sourceforge.net/projects/algol68/files/algol68toc/algol68toc-1.8.8d/algol68toc-1.8-8d.fc9.i386.rpm/download 1.8-8d] - due to extensive use of '''format'''[ted] ''transput''.}} |
{{wont work with|ELLA ALGOL 68|Any (with appropriate job cards) - tested with release [http://sourceforge.net/projects/algol68/files/algol68toc/algol68toc-1.8.8d/algol68toc-1.8-8d.fc9.i386.rpm/download 1.8-8d] - due to extensive use of '''format'''[ted] ''transput''.}} |
||
'''File: Mixin_Big_float_multiplication.a68''' |
'''File: Mixin_Big_float_multiplication.a68''' |
||
⚫ | |||
<lang algol68># Kudos: use http://en.wikipedia.org/wiki/Karatsuba_algorithm # |
|||
⚫ | |||
OP * = (DIGITS a, DIGIT b)DIGITS: a * INITDIGITS b; |
OP * = (DIGITS a, DIGIT b)DIGITS: a * INITDIGITS b; |
||
Line 83: | Line 82: | ||
INT digit width := 1; # define how decimal digits each "big" DIGIT is # |
INT digit width := 1; # define how decimal digits each "big" DIGIT is # |
||
COMMENT |
|||
Source code for Big_float_BCD_base, Mixin_Big_float_addition & subtraction |
|||
located at: http://rosettacode.org/wiki/Generalised_floating_point_additio#ALGOL_68 |
|||
END COMMENT |
|||
# include the basic axioms of the digits being used # |
# include the basic axioms of the digits being used # |
||
PR READ "Big_float_BCD_base.a68" PR |
PR READ "Big_float_BCD_base.a68" PR |
||
PR READ "Mixin_Big_float_addition.a68" PR |
PR READ "Mixin_Big_float_addition.a68" PR |
||
PR READ "Mixin_Big_float_subtraction.a68" PR |
PR READ "Mixin_Big_float_subtraction.a68" PR |
||
# Generalised multiplication # |
|||
PR READ "Mixin_Big_float_multiplication.a68" PR |
PR READ "Mixin_Big_float_multiplication.a68" PR |
||
Revision as of 10:31, 30 October 2011
If possible, define multiplication for floating point numbers where the digits are stored in an arbitrary base. eg. the digits cab be stored as binary, decimal, Binary-coded decimal, or even Balanced ternary.
Implement the code in a generalised form (such as a Template, Module or Mixin etc) that permits reusing of the code for different Bases.
If it is not possible to implement code in syntax of the specific language then:
- note the reason.
- perform test case using a built-in or external library.
Test case:
Use the Template to define Arbitrary precision multiplication on numbers stored in Binary Coded Decimal.
Number | Term calculation | Result |
---|---|---|
-8 | 111111111e63**2 x 81 + 2e135 - 1e126 | 1e144 |
-7 | 111111111111111111e54**2 x 81 + 2e126 - 1e108 | 1e144 |
-6 | 111111111111111111111111111e45**2 x 81 + 2e117 - 1e90 | 1e144 |
-5 | 111111111111111111111111111111111111e36**2 x 81 + 2e108 - 1e72 | 1e144 |
etc. | The last calculation will be with floating point numbers of more then 500 digits | 1e144 |
Note: The results will always be 1e144.
The Template should successfully handle these multiplications in other bases.
ALGOL 68
File: Mixin_Big_float_multiplication.a68 <lang algol68>OP * = (DIGIT a, DIGITS b)DIGITS: INITDIGITS a * b; OP * = (DIGITS a, DIGIT b)DIGITS: a * INITDIGITS b;
OP * = (DIGITS in a, in b)DIGITS:(
- Note: is cast really needed? eg. []STRUCTDIGIT(~) #
[]DIGIT a = digit OF []STRUCTDIGIT(digits OF in a); []DIGIT b = digit OF []STRUCTDIGIT(digits OF in b); [digit order + MSD in a+MSD in b: LSD in a+LSD in b]DIGIT a times b;
DIGIT zero := digit OF (INITSTRUCTDIGIT 0);
FOR place FROM LSD in a+LSD in b BY digit order TO LSD in a+MSD in b DO a times b[place] := zero OD; FOR place a FROM LSD in a BY digit order TO MSD in a DO DIGIT digit a = a[place a]; DIGIT carry := zero; FOR place b FROM LSD in b BY digit order TO MSD in b DO DIGIT digit b = b[place b]; REF DIGIT digit ab = a times b[place a + place b];
IF digit carry THEN # used for big number arithmetic # MOID(carry := ( digit ab +:= carry )); DIGIT prod := digit a; MOID(carry +:= ( prod *:= digit b )); MOID(carry +:= ( digit ab +:= prod )) ELSE DIGIT prod := digit a; MOID(prod *:= digit b); MOID(digit ab +:= prod) FI OD; a times b[place a + MSD in b + digit order] := carry OD;
INITDIGITS digits normalise(a times b)
);</lang>File: test_Big_float_BCD_multiplication.a68 <lang algol68>#!/usr/local/bin/a68g --script #
- A program to test abritary length BCD floating point addition. #
PR READ "prelude/general.a68" PR
INT digit width := 1; # define how decimal digits each "big" DIGIT is #
COMMENT
Source code for Big_float_BCD_base, Mixin_Big_float_addition & subtraction located at: http://rosettacode.org/wiki/Generalised_floating_point_additio#ALGOL_68
END COMMENT
- include the basic axioms of the digits being used #
PR READ "Big_float_BCD_base.a68" PR PR READ "Mixin_Big_float_addition.a68" PR PR READ "Mixin_Big_float_subtraction.a68" PR
- Generalised multiplication #
PR READ "Mixin_Big_float_multiplication.a68" PR
test: (
BIGREAL pattern = INITBIGREAL 111111111, INT pattern width = 9;
BIGREAL sum := INITBIGREAL 0, shifted pattern := pattern, tiny := INITBIGREAL 2, # typically 0.000.....00002 # very tiny := INITBIGREAL -1;# typically 0.000.....00001 #
INT start = -8;
FOR term FROM start TO 20 DO
# First make shifted pattern smaller by shifting right by the pattern width # digits OF shifted pattern := (digits OF shifted pattern)[@term*pattern width+1]; digits OF tiny := (digits OF tiny)[@(term+start+1)*pattern width]; digits OF very tiny := (digits OF very tiny)[@2*(term+1)*pattern width];
MOID(sum +:= shifted pattern);
# Manually multiply by 81 by repeated addition # BIGREAL prod := sum * sum * INITBIGREAL 81;
BIGREAL total = prod + tiny + very tiny;
IF term < -4 THEN print(( REPR sum,"**2 x 81 gives: ", REPR prod, ", Plus:",REPR tiny, " + ",REPR very tiny, ", Gives: ")) ELSE print((LSD prod - MSD prod + 1," digit test result: ")) FI; printf(($g$, REPR total, $" => "b("Passed","Failed")"!"$, LSD total = MSD total, $l$))
OD
)</lang> Output:
111111111e63**2 x 81 gives: 999999998000000001e126, Plus:2e135 + -1e126, Gives: 1e144 => Passed! 111111111111111111e54**2 x 81 gives: 999999999999999998000000000000000001e108, Plus:2e126 + -1e108, Gives: 1e144 => Passed! 111111111111111111111111111e45**2 x 81 gives: 999999999999999999999999998000000000000000000000000001e90, Plus:2e117 + -1e90, Gives: 1e144 => Passed! 111111111111111111111111111111111111e36**2 x 81 gives: 999999999999999999999999999999999998000000000000000000000000000000000001e72, Plus:2e108 + -1e72, Gives: 1e144 => Passed! +90 digit test result: 1e144 => Passed! +108 digit test result: 1e144 => Passed! +126 digit test result: 1e144 => Passed! +144 digit test result: 1e144 => Passed! +162 digit test result: 1e144 => Passed! +180 digit test result: 1e144 => Passed! +198 digit test result: 1e144 => Passed! +216 digit test result: 1e144 => Passed! +234 digit test result: 1e144 => Passed! +252 digit test result: 1e144 => Passed! +270 digit test result: 1e144 => Passed! +288 digit test result: 1e144 => Passed! +306 digit test result: 1e144 => Passed! +324 digit test result: 1e144 => Passed! +342 digit test result: 1e144 => Passed! +360 digit test result: 1e144 => Passed! +378 digit test result: 1e144 => Passed! +396 digit test result: 1e144 => Passed! +414 digit test result: 1e144 => Passed! +432 digit test result: 1e144 => Passed! +450 digit test result: 1e144 => Passed! +468 digit test result: 1e144 => Passed! +486 digit test result: 1e144 => Passed! +504 digit test result: 1e144 => Passed! +522 digit test result: 1e144 => Passed!