13,451,389 members (50,105 online)
alternative version

#### Stats

27K views
14 bookmarked
Posted 15 Apr 2013

# CKRFloat - Arbitrary Precision Calculations

, 22 Apr 2013
Arbitrary precision calculations

## Introduction

Unfortunately I found a bug in the division function. I have updated the source.

Arbitrary precision is a lot of fun. In my spare time, I create deep zoom fractal movies. I have developed my own class for calculations with many decimals, and it turned out to be many times faster than other similar classes that you can find on the Internet, referred from sites like Wikipedia and other developer forums. That is why I wanted to share my findings. This article only describes my class briefly. If you want further details, please download the code and examine it.

My class should be a starting point for further development, since it has some drawbacks that can be solved with some further hard work that might increase the speed further.

## Background

I have previously tried to use decNumber to render deep zoomed fractals, however since it is not possible to control the precision in run-time, rendering of the fractals takes about as much time when they are deep zoomed as when they are zoomed only a little. So I had to develop my own class for calculations with many decimals where I could increase the precision as the zoom gets deeper.

I only implemented the four standard arithmetic operations. Basically, I put several digits per integer in an integer array, and use the same methods that I did by hand in primary school, however treating each integer the same way as one treats each digit when doing it by hand.

Each 64-bit integer in the array can contain 8 digits, i.e., values between 0 and 100'000'000-1. Despite the low number of digits in each integer, there is no need to handle overflow when doing the actual multiplications, additions or subtraction. After the calculation loop, the array is looped through once again, and overflow is handled. This second loop is neglect-able compared to the nested loop of a multiplication.

In this way, a multiplication, which is to me the most interesting of the operations, is implemented as a `for`-loop with an inner `for`-loop. When I tested the performance, I realized that if the code inside the inner `for`-loop is as little as possible, the calculation is performed significantly faster. Even a simple comparison is costly and must be avoided. So in the end, the inner loop of my implementation contains one single line of code!

The least significant value is stored first in the array. I have been thinking back and forth of if this was a good decision. However it is easy to expand values by appending integers in the end of the list, and it would be more time consuming to push new integers in the beginning of the list and offset the whole array.

There might be a drawback to use base 10, since I am using integer divisions and modulus to handle overflow - a base-2 class could use bit wise AND and bit wise shift operations instead, which are known to be much faster.

Now with 64-bit Windows, `__int64` is a native variable, and that speeds up the calculations significantly. I am able to easily create zoom movies that zoom more than hundreds decimals, i.e. 1e100. But I want to zoom much deeper, so I tried to find other arbitrary calculation modules on the internet, and I found 3 of them. The first one, `apfloat`, is not fair to compare with my class. It is designed to be able to use millions or even billions of decimals, and therefore use heap memory or even file storage. The other two are `decNumber`, now updated to support 64-bit, and the 64-bit library ttmath. I found out that my class is more than 3 times faster than `decNumber`, and more than 7 times faster than `ttmath`, when it comes to multiplying two 300-digit values. Also addition and subtraction is performed almost twice as fast as the others.

Division is not my big concern and I thought it was a pain to implement it. I needed to implement it to calculate the offset between pixels when rendering the fractals. However the dividing is just needed a couple of times when rendering a fractal - compared to the other arithmetic operations that are needed millions or sometimes billions of times.

The times below are in seconds for multiplying 10´000 times, adding and subtracting 100'000 times, and dividing 1´000 times with two 200 digit values, generated randomly. Similar differences were measured for other lengths of the values. Assignments of the variables were not included in the measurements.
The test was performed many times on a laptop with 64-bit Windows. Since Windows kind of have it's own life and doing all kind of background processing and swappings, the lowest value for each measurement was selected - after some runs one find a value not less exceeded.

 Library Multiplication Addition Subtraction Division CKRFloat 0.014 0.026 0.026 0.032 decNumber 0.040 (286%) 0.048 (185%) 0.048 (185%) 0.026 (81%) ttmath 0.084 (600%) 0.046 (177%) 0.054 (208%) 0.028 (88%)

In addition, there is an optimization that can be done when multiplying a value with itself, i.e., squaring, which reduces the time by almost 20%. This is applicable when rendering fractals, so it is implemented in `CKRFloat`.

## Using the Code

`CKRFloat `can be used in an algebraic way:

```#include <stdio.h>
#include "CKRFloat.h"
void main()
{
CKRFloat a=23.3, b="18.12321", c=a*b;
printf("%s",c.ToText());
} ```

## History

• First revision
• Corrected some typos
• Changed type from Tips/trick to Article and on a request added info about the measurement.
• The division measurement was not correct; a fair comparison should give results with similar number of digits, so when a maximum precision was set in CKRFloat the value was updated.
• Bug fix in division (2013-04-19)

## Share

 Software Developer (Senior) Sweden
No Biography provided

## You may also be interested in...

 First PrevNext
 Unable to extract the zip Amarnath S2-Aug-14 7:12 Amarnath S 2-Aug-14 7:12
 My vote of 5 Mihai MOGA10-May-13 18:38 Mihai MOGA 10-May-13 18:38
 Re: My vote of 5 Karl Runmo10-May-13 23:10 Karl Runmo 10-May-13 23:10
 comparing to ttmath - not confirmed Member 999789618-Apr-13 16:47 Member 9997896 18-Apr-13 16:47
 Re: comparing to ttmath - not confirmed Karl Runmo18-Apr-13 20:38 Karl Runmo 18-Apr-13 20:38
 Re: comparing to ttmath - not confirmed JohnWallis4220-Apr-13 2:46 JohnWallis42 20-Apr-13 2:46
 Re: comparing to ttmath - not confirmed Karl Runmo20-Apr-13 21:30 Karl Runmo 20-Apr-13 21:30
 Re: comparing to ttmath - not confirmed JohnWallis4221-Apr-13 3:02 JohnWallis42 21-Apr-13 3:02
 Re: comparing to ttmath - not confirmed Karl Runmo21-Apr-13 7:39 Karl Runmo 21-Apr-13 7:39
 Re: comparing to ttmath - not confirmed JohnWallis4222-Apr-13 2:17 JohnWallis42 22-Apr-13 2:17
 Re: comparing to ttmath - not confirmed Karl Runmo22-Apr-13 3:13 Karl Runmo 22-Apr-13 3:13
 Re: comparing to ttmath - not confirmed JohnWallis4222-Apr-13 18:08 JohnWallis42 22-Apr-13 18:08
 Re: comparing to ttmath - not confirmed Karl Runmo22-Apr-13 21:11 Karl Runmo 22-Apr-13 21:11
 Re: comparing to ttmath - not confirmed JohnWallis4223-Apr-13 2:22 JohnWallis42 23-Apr-13 2:22
 Re: comparing to ttmath - not confirmed Karl Runmo24-Apr-13 11:44 Karl Runmo 24-Apr-13 11:44
 Re: comparing to ttmath - not confirmed JohnWallis4224-Apr-13 14:24 JohnWallis42 24-Apr-13 14:24
 Re: comparing to ttmath - not confirmed JohnWallis4224-Apr-13 17:07 JohnWallis42 24-Apr-13 17:07
 Re: comparing to ttmath - not confirmed JackDingler24-Apr-13 10:35 JackDingler 24-Apr-13 10:35
 Re: comparing to ttmath - not confirmed Karl Runmo24-Apr-13 11:49 Karl Runmo 24-Apr-13 11:49
 Re: comparing to ttmath - not confirmed Karl Runmo21-Apr-13 11:32 Karl Runmo 21-Apr-13 11:32
 Re: comparing to ttmath - not confirmed Tomasz Sowa21-Apr-13 18:49 Tomasz Sowa 21-Apr-13 18:49
 Karl Runmo wrote:What compiler do you use? I have used clang 3.2: ```\$ clang++ -v FreeBSD clang version 3.2 (tags/RELEASE_32/final 170710) 20121221 Target: x86_64-unknown-freebsd10.0 Thread model: posix``` Karl Runmo wrote:I think you need to add `#define _WIN64` Good point, this speeds up ckrf, only I have to change __int64 to int64_t as the first one is Windows specific. I prepared a new test where first some 200-digits values are prepared and then the multiplication is performed. ckrf: http://pastebin.com/YrMRKYfK[^] ttmath: http://pastebin.com/n7PdU6FV[^] let we first try ckrf: ```\$ clang++ -O2 -s -march=native -o mul_ckrf mul_ckrf.cpp CKRFloat.cpp \$ ./mul_ckrf time: 214``` now ttmath -- the first test (the size of the mantissa is exactly large to store 200 decimal digits): ```\$ clang++ -O2 -s -march=native -o mul_ttmath -I../ttmath mul_ttmath.cpp \$ ./mul_ttmath mantissa size in the machine words: 11 time: 124``` As you see ttmath is faster, but the problem is when we want all the digits from the multiplication. If we multiply 200-digits number by a 200-digits number we can have a 400-digit value. In ttmath we can achieve it only by getting a two times larger mantissa. So let we make a second test with ttmath when the mantissa is two times larger: ```\$ clang++ -O2 -s -march=native -o mul_ttmath -I../ttmath -DSECOND_TEST mul_ttmath.cpp \$ ./mul_ttmath mantissa size in the machine words: 22 time: 382``` And now ttmath is slower. It is slower because ttmath is operating on the whole mantissa, it doesn't care about the real value of the mantissa, even if the mantissa is equal to one the ttmath is performing the same calculation as it would have all the digits set. So in above test ttmath is doing twice much calculations than ckrf. Currently ttmath lacks the variable size mantissas/exponents and if you need such a feature then ttmath is not a good choise. Summarizing =========== If you want to compare (for speed) two libraries or programs first you should check what algorithms they used especially their computational complexity: https://en.wikipedia.org/wiki/Computational_complexity_theory[^] Your library for multiplication uses such a code: ```KRFLOAT_TYPE pResValues[KRFLOAT_ENTRIES+KRFLOAT_ENTRIES]; for(a=0;a small_number; ttmath::Big<1, 100> medium_number; ttmath::Big<1, 1000> large_number; but this is only a workaround and is not convenient for programming. You can give a try for GMP (it has a variable size numbers and better algorithms for multiplying than Karatsuba): http://gmplib.org/[^] and mpfr: http://www.mpfr.org/[^] GMP is treated as a standard for high precision arithmetic but I remember there were some problems when compiling on Windows in the past. For windows probably mpir would be better but I have never used it (this is a fork of GMP): http://www.mpir.org/[^]
 Re: comparing to ttmath - not confirmed Karl Runmo22-Apr-13 0:55 Karl Runmo 22-Apr-13 0:55
 Have you looked at boost multiprecision John Bandela18-Apr-13 8:12 John Bandela 18-Apr-13 8:12
 Re: Have you looked at boost multiprecision Karl Runmo18-Apr-13 21:59 Karl Runmo 18-Apr-13 21:59
 Re: Have you looked at boost multiprecision John Bandela19-Apr-13 10:56 John Bandela 19-Apr-13 10:56
 Last Visit: 31-Dec-99 18:00     Last Update: 20-Mar-18 10:03 Refresh 12 Next »