Generalised floating point multiplication: Difference between revisions

From Rosetta Code
Content added Content deleted
(Change the test case to Balance Ternary. Generate a 'Balance Ternary' multiplication table)
(remove kudos and suggest Karatsuba algorithm as an option.)
Line 1: Line 1:
{{Template:Draft task}}
{{Template:Draft task}}
Use the [[Generalised floating point addition]] template to implement generalised floating point multiplication for a
[[wp:Balanced ternary|Balanced ternary]] is a way of representing numbers. Unlike the prevailing binary representation, a balanced ternary "real" is in base 3, and each digit can have the values 1, 0, or −1. For example, decimal 11 = 3<sup>2</sup> + 3<sup>1</sup> − 3<sup>0</sup>, thus can be written as "++−", while 6 = 3<sup>2</sup> − 3<sup>1</sup> + 0 × 3<sup>0</sup>, i.e., "+−0" and for an actual real number 6⅓ the ''exact'' representation is 3<sup>2</sup> − 3<sup>1</sup> + 0 × 3<sup>0</sup> + 1 × 3<sup>-1</sup> i.e., "+−0.+"
[[wp:Balanced ternary|Balanced ternary]] test case.

'''Test case details''':
Balanced ternary is a way of representing numbers. Unlike the prevailing binary representation, a balanced ternary "real" is in base 3, and each digit can have the values 1, 0, or −1. For example, decimal 11 = 3<sup>2</sup> + 3<sup>1</sup> − 3<sup>0</sup>, thus can be written as "++−", while 6 = 3<sup>2</sup> − 3<sup>1</sup> + 0 × 3<sup>0</sup>, i.e., "+−0" and for an actual real number 6⅓ the ''exact'' representation is 3<sup>2</sup> − 3<sup>1</sup> + 0 × 3<sup>0</sup> + 1 × 3<sup>-1</sup> i.e., "+−0.+"


For this task, implement balanced ternary representation of real numbers with the following:
For this task, implement balanced ternary representation of real numbers with the following:
Line 11: Line 15:
# Make your implementation efficient, with a reasonable definition of "efficient" (and with a reasonable definition of "reasonable").
# Make your implementation efficient, with a reasonable definition of "efficient" (and with a reasonable definition of "reasonable").
# The Template should successfully handle these multiplications in other bases. In particular [[wp:Septemvigesimal|Septemvigesimal]] and "Balanced base-27".
# The Template should successfully handle these multiplications in other bases. In particular [[wp:Septemvigesimal|Septemvigesimal]] and "Balanced base-27".

Optionally:
* For faster ''long'' multiplication use [[wp:Karatsuba_algorithm|Karatsuba algorithm]].
* Using the Karatsuba algorithm, spread the computation across multiple CPUs.


'''Test case 1''' - With balanced ternaries ''a'' from string "+-0++0+.+-0++0+", ''b'' from native real -436.436, ''c'' "+-++-.+-++-":
'''Test case 1''' - With balanced ternaries ''a'' from string "+-0++0+.+-0++0+", ''b'' from native real -436.436, ''c'' "+-++-.+-++-":
Line 50: Line 58:
{{works with|ALGOL 68G|Any - tested with release [http://sourceforge.net/projects/algol68/files/algol68g/algol68g-2.3.3 algol68g-2.3.3].}}
{{works with|ALGOL 68G|Any - tested with release [http://sourceforge.net/projects/algol68/files/algol68g/algol68g-2.3.3 algol68g-2.3.3].}}
{{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: Template.Big_float.Multiplication.a68'''<lang algol68># Kudos: use http://en.wikipedia.org/wiki/Karatsuba_algorithm #
'''File: Template.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 *:= = (REF DIGITS lhs, DIGIT arg)DIGITS: lhs := lhs * INITDIGITS arg;

##########################################
# TASK CODE #
# TASK CODE #
# Actual generic mulitplication operator #
# Actual generic mulitplication operator #
##########################################
##########################################
# Alternatively use http://en.wikipedia.org/wiki/Karatsuba_algorithm #


OP * = (DIGITS a, b)DIGITS: (
OP * = (DIGITS a, b)DIGITS: (
Line 105: Line 107:
INITDIGITS a times b # normalise #
INITDIGITS a times b # normalise #
FI
FI
);
);</lang>'''File: Template.Balanced_ternary_float.Base.a68'''<lang algol68>PR READ "Template.Big_float_BCD.Base.a68" PR # [[rc:Generalised floating point addition]] #

######################################
# Define the hybrid multiplication #
# operators for the generalised base #
######################################

OP * = (DIGIT a, DIGITS b)DIGITS: INITDIGITS a * b;
OP * = (DIGITS a, DIGIT b)DIGITS: a * INITDIGITS b;

OP *:= = (REF DIGITS lhs, DIGIT arg)DIGITS: lhs := lhs * INITDIGITS arg;
</lang>'''File: Template.Balanced_ternary_float.Base.a68'''<lang algol68>PR READ "Template.Big_float_BCD.Base.a68" PR # [[rc:Generalised floating point addition]] #


################################################################
################################################################
Line 174: Line 187:
"b =",INITLONGREAL b, REPR b,
"b =",INITLONGREAL b, REPR b,
"c =",INITLONGREAL c, REPR c,
"c =",INITLONGREAL c, REPR c,
"a*(b-c)",INITREAL(a*(b-c)), REPR(a*(b-c)),
"a*(b-c)",INITLONGREAL(a*(b-c)), REPR(a*(b-c)),
$l$))
$l$))
);
);
Line 200: Line 213:
OD
OD
)</lang>'''Output:'''
)</lang>'''Output:'''
<pre style="height:15ex;overflow:scroll">
<pre>
a = +523.23914037494284407864655 +-0++0+.+-0++0+
a = +523.23914037494284407864655 +-0++0+.+-0++0+
b = -436.43600000000000000000000 --++-0--.--0+-00+++-0-+---0-+0++++0--0000+00-+-+--+0-0-00--++0-+00---+0+-+++0+-0----0++
b = -436.43600000000000000000000 --++-0--.--0+-00+++-0-+---0-+0++++0--0000+00-+-+--+0-0-00--++0-+00---+0+-+++0+-0----0++
c = +65.26748971193415637860082 +-++-.+-++-
c = +65.26748971193415637860082 +-++-.+-++-
a*(b-c) -385143.87484393900000000000 --+-+++0-00++-.0+0+0++-0++00+--00+--0-00++-++-00+-+--000---+--0----000+++-0++0-++00-++0+00-00-00++++
a*(b-c) -385143.87484393944569317497 --+-+++0-00++-.0+0+0++-0++00+--00+--0-00++-++-00+-+--000---+--0----000+++-0++0-++00-++0+00-00-00++++


# | * |+ #1 |+- #2 |+0 #3 |++ #4 |+-- #5 |+-0 #6 |+-+ #7 |+0- #8 |+e+- #9|+0+ #10|++- #11|++0 #12|
# | * |+ #1 |+- #2 |+0 #3 |++ #4 |+-- #5 |+-0 #6 |+-+ #7 |+0- #8 |+e+- #9|+0+ #10|++- #11|++0 #12|

Revision as of 09:52, 15 November 2011

Generalised floating point multiplication is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

Use the Generalised floating point addition template to implement generalised floating point multiplication for a Balanced ternary test case.

Test case details: Balanced ternary is a way of representing numbers. Unlike the prevailing binary representation, a balanced ternary "real" is in base 3, and each digit can have the values 1, 0, or −1. For example, decimal 11 = 32 + 31 − 30, thus can be written as "++−", while 6 = 32 − 31 + 0 × 30, i.e., "+−0" and for an actual real number 6⅓ the exact representation is 32 − 31 + 0 × 30 + 1 × 3-1 i.e., "+−0.+"

For this task, implement balanced ternary representation of real numbers with the following:

Requirements

  1. Support arbitrary precision real numbers, both positive and negative;
  2. Provide ways to convert to and from text strings, using digits '+', '-' and '0' (unless you are already using strings to represent balanced ternary; but see requirement 5).
  3. Provide ways to convert to and from native integer and real type (unless, improbably, your platform's native integer type is balanced ternary). If your native integers can't support arbitrary length, overflows during conversion must be indicated.
  4. Provide ways to perform addition, negation and multiplication directly on balanced ternary integers; do not convert to native integers first.
  5. Make your implementation efficient, with a reasonable definition of "efficient" (and with a reasonable definition of "reasonable").
  6. The Template should successfully handle these multiplications in other bases. In particular Septemvigesimal and "Balanced base-27".

Optionally:

  • For faster long multiplication use Karatsuba algorithm.
  • Using the Karatsuba algorithm, spread the computation across multiple CPUs.

Test case 1 - With balanced ternaries a from string "+-0++0+.+-0++0+", b from native real -436.436, c "+-++-.+-++-":

  • write out a, b and c in decimal notation.
  • calculate a × (bc), write out the result in both ternary and decimal notations.
  • In the above limit the precision to 81 ternary digits after the point.

Test case 2 - Generate a multiplication table of balanced ternaries where the rows of the table are for a 1st factor of 1 to 27, and the column of the table are for the second factor of 1 to 12.

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 the test case using a built-in or external library.

ALGOL 68

Works with: ALGOL 68 version Revision 1 - one minor extension to language used - PRAGMA READ, similar to C's #include directive.
Works with: ALGOL 68G version Any - tested with release algol68g-2.3.3.

File: Template.Big_float.Multiplication.a68<lang algol68>##########################################

  1. TASK CODE #
  2. Actual generic mulitplication operator #
  3. Alternatively use http://en.wikipedia.org/wiki/Karatsuba_algorithm #

OP * = (DIGITS a, b)DIGITS: (

 DIGITS minus one = -IDENTITY LOC DIGITS,
        zero = ZERO LOC DIGITS,
        one = IDENTITY LOC DIGITS;
 INT order = digit order OF arithmetic;
 IF SIGN a = 0 OR SIGN b = 0 THEN zero

CO # Note: The following require the inequality operators #

 ELIF a = one THEN b
 ELIF b = one THEN a
 ELIF a = minus one THEN -b
 ELIF b = minus one THEN -a

END CO

 ELSE
   DIGIT zero = ZERO LOC DIGIT;
   DIGIT one =  IDENTITY LOC DIGIT;
   [order + MSD a+MSD b: LSD a+LSD b]DIGIT a times b;
   FOR place FROM LSD a+LSD b BY order TO LSD a+MSD b DO
     a times b[place] := zero # pad the MSDs of the result wiht Zero #
   OD;
   FOR place a FROM LSD a BY order TO MSD a DO
     DIGIT digit a = a[place a];
     DIGIT carry := zero;
     FOR place b FROM LSD b BY order TO MSD b DO
       DIGIT digit b = b[place b];
       REF DIGIT digit ab = a times b[place a + place b];
       IF SIGN digit b /= 0 THEN # zero optimisation #
         IF carry OF arithmetic 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 # carry = 0 so we can just ignore the carry #
           DIGIT prod := digit a;
           MOID(prod *:= digit b);
           MOID(digit ab +:= prod)
         FI
       FI
     OD;
     a times b[place a + MSD b + order] := carry
   OD;
   INITDIGITS a times b # normalise #
 FI

);

  1. Define the hybrid multiplication #
  2. operators for the generalised base #

OP * = (DIGIT a, DIGITS b)DIGITS: INITDIGITS a * b; OP * = (DIGITS a, DIGIT b)DIGITS: a * INITDIGITS b;

OP *:= = (REF DIGITS lhs, DIGIT arg)DIGITS: lhs := lhs * INITDIGITS arg; </lang>File: Template.Balanced_ternary_float.Base.a68<lang algol68>PR READ "Template.Big_float_BCD.Base.a68" PR # rc:Generalised floating point addition #

  1. First: define the attributes of the arithmetic we are using. #

CO STRUCT (

 BOOL balanced,
      carry, # aka "carry" between digits #
 INT base,
     digit width,
     digit places,
     digit order,
 USTRING repr

) CO arithmetic := (

 # balanced = # TRUE, 
 # carry = # TRUE, 
 # base = # 3, # width = # 1, # places = # 81, # order = # -1, 
 # repr = # USTRING("-","0","+")[@-1]

);

OP INITDIGIT = (CHAR c)DIGIT: (

 DIGIT out;
 digit OF out :=
   IF   c = "+" THEN +1
   ELIF c = "0" THEN  0
   ELIF c = "-" THEN -1
   ELSE raise value error("Unknown digit :"""+c+""""); SKIP
   FI;
 out

);

OP INITBIGREAL = (STRING s)BIGREAL: (

 BIGREAL out;
 BIGREAL base of arithmetic = INITBIGREAL base OF arithmetic; # Todo: Opt #
 INT point := UPB s-1; # put the point on the extreme right #
 FOR i FROM LWB s TO UPB s DO
   IF s[i]="." THEN
     point := i
   ELSE
     out := out SHR digit order OF arithmetic + INITDIGIT s[i]
   FI
 OD;
 out SHR (UPB s-point)

);</lang>File: test.Balanced_ternary_float.Multiplication.a68<lang algol68>#!/usr/local/bin/a68g --script #

  1. A program to test abritary length floating point multiplication. #

PR READ "prelude/general.a68" PR # rc:Template:ALGOL 68/prelude #

PR READ "Template.Big_float.Multiplication.a68" PR

  1. INT digit width := 1; ## define how digits each "big" DIGIT is #
  1. include the basic axioms of the digits being used #

PR READ "Template.Balanced_ternary_float.Base.a68" PR PR READ "Template.Big_float.Addition.a68" PR # rc:Generalised floating point addition # PR READ "Template.Big_float.Subtraction.a68" PR # rc:Generalised floating point addition #

test1:( # Basic arithmetic #

 INT rw = long real width;
 BIGREAL a = INITBIGREAL "+-0++0+.+-0++0+", # 523.239... #
         b = INITBIGREAL - LONG 436.436,
         c = INITBIGREAL "+-++-.+-++-"; # 65.267... #
 printf(($g 9k g(rw,rw-5)39kgl$,
   "a =",INITLONGREAL a, REPR a,
   "b =",INITLONGREAL b, REPR b,
   "c =",INITLONGREAL c, REPR c,
   "a*(b-c)",INITLONGREAL(a*(b-c)), REPR(a*(b-c)),
 $l$))

);

test2:( # A floating point Ternary multiplication table #

 FORMAT s = $"|"$; # field seperator #
 INT lwb = 1, tab = 8, upb = 12;
 printf($"# "f(s)" *   "f(s)$);
 FOR j FROM lwb TO upb DO
   FORMAT col = $n(tab)k f(s)$;
   printf(($g" #"g(0)f(col)$, REPR INITBIGREAL j,j))
 OD;
 printf($l$);
 FOR i FROM lwb TO 27 DO
   printf(($g(0) 3k f(s) g 9k f(s)$,i,REPR INITBIGREAL i));
   FOR j FROM lwb TO i MIN upb DO
     FORMAT col = $n(tab)k f(s)$;
     BIGREAL product = INITBIGREAL i * INITBIGREAL j;
     printf(($gf(col)$, REPR product))
   OD;
   IF upb > i THEN printf($n(upb-i)(n(tab-1)x f(s))$) FI;
   printf($l$)
 OD

)</lang>Output:

a =     +523.23914037494284407864655  +-0++0+.+-0++0+
b =     -436.43600000000000000000000  --++-0--.--0+-00+++-0-+---0-+0++++0--0000+00-+-+--+0-0-00--++0-+00---+0+-+++0+-0----0++
c =      +65.26748971193415637860082  +-++-.+-++-
a*(b-c) -385143.87484393944569317497  --+-+++0-00++-.0+0+0++-0++00+--00+--0-00++-++-00+-+--000---+--0----000+++-0++0-++00-++0+00-00-00++++

# | *   |+ #1   |+- #2  |+0 #3  |++ #4  |+-- #5 |+-0 #6 |+-+ #7 |+0- #8 |+e+- #9|+0+ #10|++- #11|++0 #12|
1 |+    |+      |       |       |       |       |       |       |       |       |       |       |       |
2 |+-   |+-     |++     |       |       |       |       |       |       |       |       |       |       |
3 |+0   |+0     |+-0    |+e+-   |       |       |       |       |       |       |       |       |       |
4 |++   |++     |+0-    |++0    |+--+   |       |       |       |       |       |       |       |       |
5 |+--  |+--    |+0+    |+--0   |+-+-   |+0-+   |       |       |       |       |       |       |       |
6 |+-0  |+-0    |++0    |+-e+-  |+0-0   |+0+0   |++e+-  |       |       |       |       |       |       |
7 |+-+  |+-+    |+---   |+-+0   |+00+   |++0-   |+---0  |+--++  |       |       |       |       |       |
8 |+0-  |+0-    |+--+   |+0-0   |++--   |++++   |+--+0  |+-0+-  |+0+    |       |       |       |       |
9 |+e+- |+e+-   |+-e+-  |+e+0   |++e+-  |+--e+- |+-e+0  |+-+e+- |+0-e+- |+e++   |       |       |       |
10|+0+  |+0+    |+-+-   |+0+0   |++++   |+-0--  |+-+-0  |+0--+  |+000-  |+0+e+- |+-0-0+ |       |       |
11|++-  |++-    |+-++   |++-0   |+--0-  |+-00+  |+-++0  |+00--  |++-+   |++-e+- |++0+-  |+++++  |       |
12|++0  |++0    |+0-0   |++e+-  |+--+0  |+-+-0  |+0-e+- |+00+0  |++--0  |++e+0  |++++0  |+--0-0 |+--+e+-|
13|+++  |+++    |+00-   |+++0   |+-0-+  |+-++-  |+00-0  |+0+0+  |++0--  |+++e+- |+-+-++ |+--+0- |+-0-+0 |
14|+--- |+---   |+00+   |+---0  |+-0+-  |+0--+  |+00+0  |++-0-  |--+0++ |+---e+-|+0+--  |+-0-0+ |+-0+-0 |
15|+--0 |+--0   |+0+0   |+--e+- |+-+-0  |+0-+0  |+0+e+- |++0-0  |--+++0 |+--e+0 |+-0--0 |+-00+0 |+-+-e+-|
16|+--+ |+--+   |++--   |+--+0  |+-+0+  |+000-  |++--0  |++0++  |+-+-   |+--+e+-|+-00-+ |+-+--- |+-+0+0 |
17|+-0- |+-0-   |++-+   |+-0-0  |+0---  |+00++  |++-+0  |++++-  |+--00+ |+-0-e+-|+++0-  |+-+0-+ |+0---0 |
18|+-e+-|+-e+-  |++e+-  |+-e+0  |+0-e+- |+0+e+- |++e+0  |+---e+-|+--+e+-|+-e++  |+-+-e+-|+-++e+-|+0-e+0 |
19|+-0+ |+-0+   |+++-   |+-0+0  |+0-++  |++---  |+++-0  |+--0-+ |+0--0- |+-0+e+-|+-+00+ |+0--+- |+0-++0 |
20|+-+- |+-+-   |++++   |+-+-0  |+000-  |++-0+  |++++0  |+--+-- |+-00-+ |+-+-e+-|++-++- |+0-0++ |+000-0 |
21|+-+0 |+-+0   |+---0  |+-+e+- |+00+0  |++0-0  |+---e+-|+--++0 |+-0+-0 |+-+e+0 |+----+0|+00--0 |+00+e+-|
22|+-++ |+-++   |+--0-  |+-++0  |+0+-+  |++0+-  |+--0-0 |+-0-0+ |+00--- |+-++e+-|+---0++|+0000- |+0+-+0 |
23|+0-- |+0--   |+--0+  |+0--0  |+0++-  |+++-+  |+--0+0 |+-000- |+-++   |+0--e+-|+00--- |+00+0+ |+0++-0 |
24|+0-0 |+0-0   |+--+0  |+0-e+- |++--0  |++++0  |+--+e+-|+-0+-0 |+0+0   |+0-e+0 |+000-0 |+0+-+0 |++--e+-|
25|+0-+ |+0-+   |+-0--  |+0-+0  |++-0+  |+---0- |+-0--0 |+-0+++ |+++-   |+0-+e+-|+00+-+ |+0++-- |++-0+0 |
26|+00- |+00-   |+-0-+  |+00-0  |++0--  |+---++ |+-0-+0 |+-+-+- |+0--0+ |+00-e+-|+0+-0- |++---+ |++0--0 |
27|+e+0 |+e+0   |+-e+0  |+e++   |++e+0  |+--e+0 |+-e++  |+-+e+0 |+0-e+0 |+e+--  |+0+e+0 |++-e+0 |++e++  |