Anonymous user
Generalised floating point multiplication: Difference between revisions
Generalised floating point multiplication (view source)
Revision as of 09:52, 15 November 2011
, 12 years agoremove kudos and suggest Karatsuba algorithm as an option.
(Change the test case to Balance Ternary. Generate a 'Balance Ternary' multiplication table) |
(remove kudos and suggest Karatsuba algorithm as an option.) |
||
Line 1:
{{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''':
▲
For this task, implement balanced ternary representation of real numbers with the following:
Line 11 ⟶ 15:
# 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".
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'' "+-++-.+-++-":
Line 50 ⟶ 58:
{{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''.}}
'''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 #
# Actual generic mulitplication operator #
##########################################
# Alternatively use http://en.wikipedia.org/wiki/Karatsuba_algorithm #
OP * = (DIGITS a, b)DIGITS: (
Line 105 ⟶ 107:
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]] #▼
# 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;
▲
################################################################
Line 174 ⟶ 187:
"b =",INITLONGREAL b, REPR b,
"c =",INITLONGREAL c, REPR c,
"a*(b-c)",
$l$))
);
Line 200 ⟶ 213:
OD
)</lang>'''Output:'''
<pre style="height:15ex;overflow:scroll">
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.
# | * |+ #1 |+- #2 |+0 #3 |++ #4 |+-- #5 |+-0 #6 |+-+ #7 |+0- #8 |+e+- #9|+0+ #10|++- #11|++0 #12|
| |||