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

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 com开发者_运维百科putation 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.

---

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.

---

Yes, just use 64 bit integers:

long val; // Java

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

---

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

---

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.

---

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.