Generalised floating point multiplication

From Rosetta Code
Revision as of 10:32, 15 November 2011 by rosettacode>NevilleDNZ (→‎{{header|ALGOL 68}}: {{incorrect|ALGOL 68|The result a*(b-c) should be about -262510.90267998143}})
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 × (b − c), 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

This example is incorrect. Please fix the code and remove this message.

Details: The result a*(b-c) should be about -262510.90267998143

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

);

  2. Define the hybrid multiplication #
  3. 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 #

  2. 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 #

  2. A program to test arbitrary length floating point multiplication #

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

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

  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++  |
Retrieved from "https://rosettacode.org/wiki/Generalised_floating_point_multiplication?oldid=204335"