[Caml-list] Fixed-point arithmetic on 32-bit architectures

[Caml-list] Fixed-point arithmetic on 32-bit architectures

[Eray Ozkural]

[-- Attachment #1: Type: text/plain, Size: 658 bytes --]

Hello there,

I'm using fixed-point arithmetic in an algorithm. I am troubled by the
inefficiency of the fixed-point multiplication and division operations on
32-bit architectures. On the Intel 64-bit architecture, I can use the
Nativeint module and it's quite fast, on 32-bit I had to use the Int64
module (for the necessary shifts and mul/div's) and I encountered a
significant slowdown, naturally. is there a preferred way of performing
fixed point arithmetic with ocaml on 32-bit architectures that I might be
overlooking?

Best,

-- 
Eray Ozkural, PhD candidate.  Comp. Sci. Dept., Bilkent University, Ankara
http://groups.yahoo.com/group/ai-philosophy

[-- Attachment #2: Type: text/html, Size: 810 bytes --]

Re: [Caml-list] Fixed-point arithmetic on 32-bit architectures

[Niki Yoshiuchi]

What range of numbers are you hoping to represent and what operations
are you commonly performing on them?  If it's possible for you to
represent your numbers as 24.8 fixed-point (for example) and you are
mostly adding and subtracting, then I would recommend using 32 bit
integers and casting to 64 bit for multiplication and division.
Alternatively you can try and be clever about your shifting instead of
casting (shifting the multiplicand instead of the product, or doing a
half shift on each multiplicand, etc).

On Wed, Jan 5, 2011 at 11:22 AM, Eray Ozkural <examachine@gmail.com> wrote:
> Hello there,
> I'm using fixed-point arithmetic in an algorithm. I am troubled by the
> inefficiency of the fixed-point multiplication and division operations on
> 32-bit architectures. On the Intel 64-bit architecture, I can use the
> Nativeint module and it's quite fast, on 32-bit I had to use the Int64
> module (for the necessary shifts and mul/div's) and I encountered a
> significant slowdown, naturally. is there a preferred way of performing
> fixed point arithmetic with ocaml on 32-bit architectures that I might be
> overlooking?
> Best,
> --
> Eray Ozkural, PhD candidate.  Comp. Sci. Dept., Bilkent University, Ankara
> http://groups.yahoo.com/group/ai-philosophy
>
>

Re: [Caml-list] Fixed-point arithmetic on 32-bit architectures

[Eray Ozkural]

[-- Attachment #1: Type: text/plain, Size: 2568 bytes --]

Hi there,

Thank you for your reply Niki.

The range of numbers is usually between 0 and 1, because I'm mostly working
on
normalized vectors.

I was using 22 bits for the decimal part but unfortunately multiplication is
a common operation. I was converting to Int64 for multiplication. I thought
about half-shifting but then I didn't try it because I thought there might
be lost
precision, on second thought it might work for me though, perhaps I can
define
it as another (risky) operation. Right-shifting each operand 11 bits before
multiplication
would save me from using any Int64 ops, or if I am certain that each operand
is
smaller than 1 I could shift right fewer bits initially to save some
precision. A
good way to do that would be to have an assert that gets turned on in debug
builds.

The safe multiplication was defined as:

  let mul x y =
    Int64.to_int
      (Int64.shift_right
         (Int64.mul (Int64.of_int x) (Int64.of_int y) ) q)

where q = 22 for me.

On Wed, Jan 5, 2011 at 6:34 PM, Niki Yoshiuchi <aplusbi@gmail.com> wrote:

> What range of numbers are you hoping to represent and what operations
> are you commonly performing on them?  If it's possible for you to
> represent your numbers as 24.8 fixed-point (for example) and you are
> mostly adding and subtracting, then I would recommend using 32 bit
> integers and casting to 64 bit for multiplication and division.
> Alternatively you can try and be clever about your shifting instead of
> casting (shifting the multiplicand instead of the product, or doing a
> half shift on each multiplicand, etc).
>
> On Wed, Jan 5, 2011 at 11:22 AM, Eray Ozkural <examachine@gmail.com>
> wrote:
> > Hello there,
> > I'm using fixed-point arithmetic in an algorithm. I am troubled by the
> > inefficiency of the fixed-point multiplication and division operations on
> > 32-bit architectures. On the Intel 64-bit architecture, I can use the
> > Nativeint module and it's quite fast, on 32-bit I had to use the Int64
> > module (for the necessary shifts and mul/div's) and I encountered a
> > significant slowdown, naturally. is there a preferred way of performing
> > fixed point arithmetic with ocaml on 32-bit architectures that I might be
> > overlooking?
> > Best,
> > --
> > Eray Ozkural, PhD candidate.  Comp. Sci. Dept., Bilkent University,
> Ankara
> > http://groups.yahoo.com/group/ai-philosophy
> >
> >
>



-- 
Eray Ozkural, PhD candidate.  Comp. Sci. Dept., Bilkent University, Ankara
http://groups.yahoo.com/group/ai-philosophy
http://myspace.com/arizanesil http://myspace.com/malfunct

[-- Attachment #2: Type: text/html, Size: 3570 bytes --]