Anonymous user
Generalised floating point multiplication: Difference between revisions
Generalised floating point multiplication (view source)
Revision as of 09:02, 15 November 2011
, 12 years agoChange the test case to Balance Ternary. Generate a 'Balance Ternary' multiplication table
m (a sequence of -7 to 21 will work here too.) |
(Change the test case to Balance Ternary. Generate a 'Balance Ternary' multiplication table) |
||
Line 1:
{{Template:Draft task}}
[[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.+"
For this task, implement balanced ternary representation of real numbers with the following:
'''Requirements'''
# Support arbitrary precision real numbers, both positive and negative;
# 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).
# 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.
# Provide ways to perform addition, negation and multiplication directly on balanced ternary integers; do ''not'' convert to native integers first.
# 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".
'''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 [[wp:Template (programming)|Template]], [[wp:Modular programming|Module]] or [[wp:Mixin|Mixin]] etc) that permits reusing of the code for different [[wp:Base_(exponentiation)#In_numeral_systems|Bases]].
Line 6 ⟶ 23:
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.
<!--
'''Test case:'''
Use the Template to define [[wp:Arbitrary-precision arithmetic|Arbitrary precision multiplication]] on numbers stored in
{|class="wikitable" style="text-align: center; margin: 1em auto 1em auto;"
Line 28 ⟶ 45:
|}
Note: The results will always be 1e144.
-->
=={{header|ALGOL 68}}==
{{works with|ALGOL 68|Revision 1 - one minor extension to language used - PRAGMA READ, similar to C's #include directive.}}
{{works with|ALGOL 68G|Any - tested with release [http://sourceforge.net/projects/algol68/files/algol68g/algol68g-2.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''.}}
'''File: Template.Big_float.Multiplication.a68'''<lang algol68># Kudos: use http://en.wikipedia.org/wiki/Karatsuba_algorithm #
OP * = (DIGIT a, DIGITS b)DIGITS: INITDIGITS a * b;
OP * = (DIGITS a, DIGIT b)DIGITS: a * INITDIGITS b;
OP *:= = (REF DIGITS
##########################################
# TASK CODE #
# Actual generic mulitplication operator #
##########################################
OP * = (DIGITS a, b)DIGITS: (
DIGITS minus one = -IDENTITY LOC DIGITS,
zero = ZERO LOC DIGITS,
INT order
IF SIGN
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
a times
OD;
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
);</lang>'''File: Template.Balanced_ternary_float.Base.a68'''<lang algol68>PR READ "Template.Big_float_BCD.Base.a68" PR # [[rc:Generalised floating point addition]] #
################################################################
# 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 #
####################################################################
# 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
# INT digit width := 1; ## define how digits each "big" DIGIT is #
# 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)",INITREAL(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($"#
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:'''
<pre>
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.87484393900000000000 --+-+++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++ |
</pre>
[[Category:Arbitrary precision]]
|