"Simulating" a 64-bit integer with two 32-bit integers

Asked 10/6, 2011 at 14:45 Answered 10/6, 2011 at 18:25

Solved java c++c 32bit-64bit large-data-volumes

I'm writing a very computationally intense procedure for a mobile device and I'm limited to 32-bit CPUs. In essence, I'm performing dot products of huge sets of data (>12k signed 16-bit integers). Floating point operations are just too slow, so I've been looking for a way to perform the same computation with integer types. I stumbled upon something called Block Floating Point arithmetic (page 17 in the linked paper). It does a pretty good job, but now I'm faced with a problem of 32 bits just not being enough to store the output of my calculation with enough precision.

Just to clarify, the reason it's not enough precision is that I would have to drastically reduce precision of each of my arrays' elements to get a number fitting into a 32-bit integer in the end. It's the summation of ~16000 things that makes my result so huge.

Is there a way (I'd love a reference to an article or a tutorial) to use two 32-bit integers as most significant word and least significant word and define arithmetic on them (+, -, *, /) to process data efficiently? Also, are there perhaps better ways of doing such things? Is there a problem with this approach? I'm fairly flexible on programming language I use. I would prefer C/C++ but java works as well. I'm sure someone has done this before.

Autophyte answered 10/6, 2011 at 14:45 Comment(6)

I have a stupid question - why can't you use a long, which is 64 bit even on a 32 bit cpu? – Knickerbockers 10/6, 2011 at 14:47

The stupid answer is yes you can. I was mislead by a piece of documentation. Thanks = ) – Autophyte 10/6, 2011 at 14:54

Consider switching to native code. – Trioecious 10/6, 2011 at 14:55

@Knickerbockers In fact long is typically 32 bits on a 32 bit system (although this isn't required) while long long if available is the 64 bit integral type. – Exsiccate 10/6, 2011 at 14:56

Not in java it ain't - on java - short is always 16 bit, integer 32 bit, long 64 bit. No long longs here – Knickerbockers 10/6, 2011 at 14:58

C++ interpretation of how many bits assign to data types is compiler dependent. In Java, you always get the same bit representation. – Autophyte 10/6, 2011 at 18:28

I'm pretty sure that the JVM must support a 64-bit arithmetic long type, and if the platform doesn't support it, then the VM must emulate it. However, if you can't afford to use float for performance problems, then a JVM will probably destroy you.

Most C and C++ implementations will provide 64-bit arithmetic emulated for 32bit targets- I know that MSVC and GCC do. However, you should be aware that you can be talking about many integer instructions to save a single floating-point instruction. You should consider that the specifications for this program are unreasonable, or perhaps that you could free performance from somewhere else.

Japan answered 10/6, 2011 at 14:49 Comment(3)

"if you can't afford to use float for performance problems, then a JVM will probably destroy you." - not true. Many phones run JVM just fine, but don't have an FPU, making floating-point operations expensive. Some of them don't even support native apps, because the OS itself is written in Java. – Wineshop 10/6, 2011 at 14:58

@BlueRaja: Sure, but the JVM costs an awful lot more to run than having to emulate floating-point. – Japan 10/6, 2011 at 15:5

Not necessarily. There are some common processors (such as the ARM926) which have no FPU, but which do have hardware acceleration to translate Java bytecode into native instructions on the fly, making Java almost as fast as native code. – Fretful 10/6, 2011 at 16:9

Yes, just use 64 bit integers:

long val; // Java

#include <stdint.h>
int64_t val; // C

Marla answered 10/6, 2011 at 14:51 Comment(0)

There is a list of libraries on the wikipedia page about Arbitrary Precision Arithmetic. Perhaps something on there would work for you?

Elianaelianora answered 10/6, 2011 at 14:50 Comment(0)

If you can use Java, the short answer is: Use Java long's. The Java standard defines a long as 64 bits. Any JVM should implement this or it is not compliant with the standard. Nothing requires the CPU to support 64-bit arithmetic. If it's not natively supported, a JVM should implement it with software.

If you really have some crippled Java that does not support long's, use BigInteger. This handles integers of any arbitrarily-large size.

Slam answered 10/6, 2011 at 14:52 Comment(0)

Talking about C/C++.
Any normal compiler would support "long long" type as 64-bit integrs with all normal arithmetic.
Combined with -O3, it gets very good chances of outputting best possible code for 64-bit arithemtic on your platform.

Sternmost answered 10/6, 2011 at 18:25 Comment(0)

Recommended topics

Hot tags