Cesky: |
LongInt
C++ library of long integer and fixed-point numbers
The original idea was to create a generic C++ library doubling the precision of basic elements, which could be used by itself to recursively increase the range of numbers. It didn't quite work, after all the compiler still has some rejection talk for such use :-) , but the library can still be used to implement larger numbers than the compiler supports. A typical use case is the ATmega processor, whose C library does not fully support 64-bit integer numbers.
The library contains 2 base classes, DblInt and QuadInt, which double and quadruple the resolution of the base elements used. Using 8 to 64-bit elements, the DblInt class can be used to create numbers of type uint32, sint32, fix32, uint64, sint64, fix64, uint128, sint128, and fix128. The QuadInt class can be used to create numbers of type uin64, sint64, fix64, uint128, sint128, fix128, uint256, sint256, and fix256. The uint* types are unsigned integer types. The sint* types are signed integers. The fix* types are fixed-point decimal numbers. The upper half of the number is the integer part, the lower half is the decimal part.
Class types are defined using the #define maker. A class file is included in the source code and the parameters are defined using #define before inclusion. The code can be included multiple times, with different parameter settings, to create different types of numbers in the program, using common library code. Alternatively, it should not be a problem to modify the code into a template.
An example use case can be seen in the sample test.cpp and test.h files used to test the library. The sample program performs library testing by generating random operands (a full PC test involves 1000000000 tests performed for each type of number). The program is ready to be compiled both under Microsoft VC++ 2005 and for the ARM processor on Raspberry Pico. Sample output of the test program:
Check dbl uint32 ... OK
123 + 7545 = 7668 (should be 7668)
Check dbl sint32 ... OK
123 * -7545 = -928035 (should be -928035)
Check dbl fix32 ... OK
123.45 / 3.1415 = 39.2966 (should be 39.2965)
Check dbl uint64 ... OK
897656 % 75452 = 67684 (should be 67684)
Check dbl sint64 ... OK
-1239851456 * 754554789 = -935535853773422784 (should be -935535853773422784)
Check dbl fix64 ... OK
sin_deg(58.76534523) = 0.855050776 (should be 0.855050780)
Check quad uint64B ... OK
45872341 xor 664334789 = 623052048 (should be 623052048)
Check quad sint64B ... OK
(-7545545)^2 = 56935249347025 (should be 56935249347025)
Check quad fix64B ... OK
457.55 ^ 1.14 = 1078.698207313 (should be 1078.698209953)
Check quad dbl uint128 ... OK
65544765565 << 12 = 268471359754240 (should be 268471359754240)
Check quad dbl sint128 ... OK
sqrt_int(65544765565) = 256017 remainder 61276 (should be 256017 remainder 61276)
quad uint256
28! = 304888344611713860501504000000 (should be 304888344611713860501504000000)
quad fix256
exp(3.1415926535897932384626433832795028842) = 23.14069263277926900572908636794854738013
(should be 23.14069263277926900572908636794854738033)
Integer types have functions for basic arithmetic operations: addition, subtraction, multiplication, division, modulo, increment, decrement, integral, comparison, negation, bitwise operations, shifts, and integer square root.
For integer types, fast division is available, designed to repeatedly divide a number by a constant. Fast division analyzes the divisor and determines the fastest operation to perform the division. In the usual cases, instead of division, it uses multiplication by the inverse of the divisor and bit-shifting of the result.
Fixed-point number types have the additional functions inverse, square root, power, angular rate conversions, sine, cosine, tangent, arcus sine, arcus cosine, arcus tangent, logarithm, exponent.
The library is not optimized for speed. It is intended to be used to fill in missing number ranges and as a reference for testing the assembler version of the library. The library package also includes an older version of the library, LongCalc, with an x64 assembler speedup of the library and an elaboration of the BigNum long fixed-point number library.
The library is not fully polished, nor 100% debugged. During the development, I came across the main drawback of fixed-point numbers - accuracy drops very quickly during computations. Typically, this can be observed, for example, in exponent and logarithm calculations, where the error quickly gets into the significant parts of the number. A more correct solution would be to perform calculations with higher precision and convert the result to the target format. More practical are numbers with an exponent. The exponent protects the number from rapid loss of precision in intermediate calculations.
Series calculations, such as sine, are not the best solution either. Series calculations should be broken into sections using different methods, otherwise in some operand bands the calculation takes too long and with lower accuracy.
In the library package you will find:
Finally, a digression - how to detect overflow of sum and difference of unsigned numbers. In assembler this is clear - there is a C and V flag. In C++ we don't have the carry flag so we have to use the following procedure. When we add the numbers, and if the result is less than any of the input numbers, an overflow has occurred:
c = a + b; bool carry = (c < b) ? 1 : 0;
When subtracting operands, subtract. Compare the input operands and if the second operand was larger than the first, an overflow occurred:
c = a - b; bool carry = (a < b) ? 1 : 0;
Link to download the library: LongInt_src.zip
Miroslav Nemecek