OT 64 Bit arithmetic.

Started by Jonathan Masters July 12, 2010
I have an LPC2000 application that is reading 32 bits from a quadrature
counter in an FPGA.

In converting the counts to user units I am using Q8 arithmetic which
involves multiplying by one parameter and dividing by another. Naturally
multiplying first is desirable to keep the precision when dividing. But
I am alternately running into one of two problems: either there aren't
enough bits to multiply first and keep a sensible range or there isn't
enough precision after division.

I have an algorithm that is a hybrid. It is unreadable code that relies
on testing with spreadsheets. I'd prefer to have a 64bit arithmetic package.

My question is (without relying on a compiler with anything other than
32bit knowledge/my compiler doesn't like long longs), are there open
source, fast(ish) integer libraries in C that I can look at to help my code?

Jonathan.

An Engineer's Guide to the LPC2100 Series

--- In l..., Jonathan Masters wrote:
> My question is (without relying on a compiler with anything other than
> 32bit knowledge/my compiler doesn't like long longs), are there open
> source, fast(ish) integer libraries in C that I can look at to help my code?
>

You might be better off doing this sort of thing in Assembler. The "ARM System Developers Guide" by Sloss, Symes and Wright has a whole chapter on "Optimized Primitives". The code is in ARM assembler and includes double-precision multiplication - multiplying 64-bit signed or unsigned integers , giving a 64-bit or 128-bit result (in less than 20 instructions).

There are several division algorithms discussed e.g. Unsigned 32-bit/32-bit, unsigned 64/31-bit.

If you haven't got the book already buy it anyway. Even if that chapter is no good to you, there's sure to be something in the rest that will come in useful.

Regards,
Chris Burrows
CFB Software

Astrobe: LPC2xxx Oberon-07 Development System
http://www.astrobe.com

On 12/07/2010 2:11 PM, cfbsoftware1 wrote:
>
> --- In l... ,
> Jonathan Masters wrote:
> >
> >
> > My question is (without relying on a compiler with anything other than
> > 32bit knowledge/my compiler doesn't like long longs), are there open
> > source, fast(ish) integer libraries in C that I can look at to help
> my code?
> > You might be better off doing this sort of thing in Assembler. The
> "ARM System Developers Guide" by Sloss, Symes and Wright has a whole
> chapter on "Optimized Primitives". The code is in ARM assembler and
> includes double-precision multiplication - multiplying 64-bit signed
> or unsigned integers , giving a 64-bit or 128-bit result (in less than
> 20 instructions).
>
> There are several division algorithms discussed e.g. Unsigned
> 32-bit/32-bit, unsigned 64/31-bit.
>
> If you haven't got the book already buy it anyway. Even if that
> chapter is no good to you, there's sure to be something in the rest
> that will come in useful.
>
> Regards,
> Chris Burrows
> CFB Software
>
> Astrobe: LPC2xxx Oberon-07 Development System
> http://www.astrobe.com
(PS I have the book, hardly opened - I pulled it off the shelf and
bizzarely it opened at page 218)
Thanks Chris,

Was trying to avoid assembler because same code is used on TI C2406 DSP
and I'd like it to port between products. If it has to be, it might have
to be.

Jonathan.

On 12/07/2010 2:11 PM, cfbsoftware1 wrote:
>
> --- In l... ,
> Jonathan Masters wrote:
> >
> >
> > My question is (without relying on a compiler with anything other than
> > 32bit knowledge/my compiler doesn't like long longs), are there open
> > source, fast(ish) integer libraries in C that I can look at to help
> my code?
> > You might be better off doing this sort of thing in Assembler. The
> "ARM System Developers Guide" by Sloss, Symes and Wright has a whole
> chapter on "Optimized Primitives". The code is in ARM assembler and
> includes double-precision multiplication - multiplying 64-bit signed
> or unsigned integers , giving a 64-bit or 128-bit result (in less than
> 20 instructions).
>
> There are several division algorithms discussed e.g. Unsigned
> 32-bit/32-bit, unsigned 64/31-bit.
>
> If you haven't got the book already buy it anyway. Even if that
> chapter is no good to you, there's sure to be something in the rest
> that will come in useful.
>
> Regards,
> Chris Burrows
> CFB Software
>
> Astrobe: LPC2xxx Oberon-07 Development System
> http://www.astrobe.com
Am 12.07.2010 06:19, schrieb Jonathan Masters:
> Thanks Chris,
>
> Was trying to avoid assembler because same code is used on TI C2406 DSP
> and I'd like it to port between products. If it has to be, it might have
> to be.

But a modern C compiler that does not support 64bit (on an ARM) is IMHO
more a porting problem than well documented assembler code. I suggest to
throw away the compiler.

--
42Bastian
+
| http://www.sciopta.com
| Fastest direct message passing kernel.
| IEC61508 certified.
+
--- In l..., Jonathan Masters wrote:
>
> Was trying to avoid assembler because same code is used on TI C2406 DSP
> and I'd like it to port between products. If it has to be, it might have
> to be.
>

Doesn't look as though it would be too difficult to adapt the pseudo-code (that is used to comment the code) to C.

Spooky that the book fell open at the right page. That has happened to me more than once in the past. You can almost hear the X Files theme tune playing ;-)

Chris.

--- In l..., Jonathan Masters wrote:
> 32bit knowledge/my compiler doesn't like long longs)

What is your compiler, that does not like longs ??

Is there really an ARM compiler that does not like longs ??!!

don

Am 12.07.2010 06:56, schrieb Donald H:
> --- In l..., Jonathan Masters wrote:
>> 32bit knowledge/my compiler doesn't like long longs)
>
> What is your compiler, that does not like longs ??
>
> Is there really an ARM compiler that does not like longs ??!!

Not 'long' 'long long' i.e. 64bit variables.
(But I don't know of any either).
--
42Bastian
+
| http://www.sciopta.com
| Fastest direct message passing kernel.
| IEC61508 certified.
+
On 12/07/2010 04:44, Jonathan Masters wrote:
> My question is (without relying on a compiler with anything other than
> 32bit knowledge/my compiler doesn't like long longs), are there open
> source, fast(ish) integer libraries in C that I can look at to help my code?

How are you trying to use 64-bit integers? 'long long' may be iffy, but
'uint64_t' and 'int64_t' (defined in , which you must include
first) should always be fine. Also, try compiling in C99 mode (-std
option, or something like that).

The alternative is the hybrid approach that I suspect you're already
using -- split the multiplies and divides into smaller chunks based on
the range you expect as input. Probably not very efficient, but more
accurate so it depends on your needs.

It may also be possible to divide by a smaller number initially and
interpret the result as a fixed point number, but without knowing what
range of values we're talking about it's hard to say for sure.

Pete

--
Pete Vidler
Senior Systems Developer,
TTE Systems Ltd

Work: http://www.tte-systems.com
Home: http://petevidler.com
Not so much that the ARM compiler does not provide a 64 bit type, but
that the other compilers on other processors in my product range do not.

I'm trying to find a broad solution for the lowest common denominator.
Actually a very lightweight floating point solution would be nice. I
did a polynomial linearization in 56 bits in PL/M on an 8051 some
years back - looks like I need to find the source for that.

Jonathan

On 12/07/2010, at 2:35 PM, 42Bastian wrote:

> Am 12.07.2010 06:19, schrieb Jonathan Masters:
> >
> >
> > Thanks Chris,
> >
> > Was trying to avoid assembler because same code is used on TI
> C2406 DSP
> > and I'd like it to port between products. If it has to be, it
> might have
> > to be.
>
> But a modern C compiler that does not support 64bit (on an ARM) is
> IMHO
> more a porting problem than well documented assembler code. I
> suggest to
> throw away the compiler.
>
> --
> 42Bastian
> +
> | http://www.sciopta.com
> | Fastest direct message passing kernel.
> | IEC61508 certified.
> +
>