Version française
Home     About     Download     Resources     Contact us    
Browse thread
[Caml-list] Does Caml have slow arithmetics ?
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: -- (:)
From: Richard Jones <rich@a...>
Subject: Re: [Caml-list] Does Caml have slow arithmetics ?
On Wed, Jul 07, 2004 at 02:32:56PM +0200, Diego Olivier Fernandez Pons wrote:
> Subsidiary question : why LSB instead of MSB ? I thought it would be
> simpler to let the computations silently overflow and correct when
> necessary the tag bit.

I don't know, but the current representation allows simplifications of
some common mathematical operations.  You don't need to worry about
the tag bit at all.

Addition (a + b)
----------------

let r1 = 2 * a + 1	# Actual representation of 'a' in a register
let r2 = 2 * b + 1

  r1 + r2 - 1		# Addition, proof follows:
= 2 * a + 1 + 2 * b + 1 - 1
= 2 * a + 2 * b + 1
= 2 * (a + b) + 1

ocamlopt actually uses the effective address calculation unit to do
this, so it's basically a single instruction:

lea     -1(%eax, %ebx), %eax

Subtractions (a - b)
--------------------

let r1 = 2 * a + 1	# Actual representation of 'a' in a register
let r2 = 2 * b + 1

  r1 - r2 + 1		# Subtraction, proof follows:
= 2 * a + 1 - 2 * b + 1 + 1
= 2 * a - 2 * b + 1
= 2 * (a - b) + 1

ocamlopt compiles this to two instructions:

subl    %ebx, %eax
incl    %eax

Multiplication (a * b)
----------------------

let r1 = 2 * a + 1	# Actual representation of 'a' in a register
let r2 = 2 * b + 1

  (r1 - 1) * (r2 / 2) + 1
= (2 * a + 1 - 1) * b + 1	# NB: r2 / 2 = b because of integer rounding
= 2 * a * b + 1
= 2 * (a * b) + 1

ocamlopt compiles this into four instructions:

sarl    $1, %ebx
decl    %eax
imull   %ebx, %eax
incl    %eax

Rich.

-- 
Richard Jones. http://www.annexia.org/ http://www.j-london.com/
Merjis Ltd. http://www.merjis.com/ - improving website return on investment
MONOLITH is an advanced framework for writing web applications in C, easier
than using Perl & Java, much faster and smaller, reusable widget-based arch,
database-backed, discussion, chat, calendaring:
http://www.annexia.org/freeware/monolith/

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners