Click here to Skip to main content
13,451,389 members (50,105 online)
Click here to Skip to main content
Add your own
alternative version


14 bookmarked
Posted 15 Apr 2013

CKRFloat - Arbitrary Precision Calculations

, 22 Apr 2013
Rate this:
Please Sign up or sign in to vote.
Arbitrary precision calculations


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.


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;


  • First revision
  • Added the source 
  • 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) 


This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


About the Author

Karl Runmo
Software Developer (Senior)
Sweden Sweden
No Biography provided

You may also be interested in...

Comments and Discussions

QuestionUnable to extract the zip Pin
Amarnath S2-Aug-14 7:12
memberAmarnath S2-Aug-14 7:12 
GeneralMy vote of 5 Pin
Mihai MOGA10-May-13 18:38
memberMihai MOGA10-May-13 18:38 
GeneralRe: My vote of 5 Pin
Karl Runmo10-May-13 23:10
memberKarl Runmo10-May-13 23:10 
Newscomparing to ttmath - not confirmed Pin
Member 999789618-Apr-13 16:47
memberMember 999789618-Apr-13 16:47 
GeneralRe: comparing to ttmath - not confirmed Pin
Karl Runmo18-Apr-13 20:38
memberKarl Runmo18-Apr-13 20:38 
GeneralRe: comparing to ttmath - not confirmed Pin
JohnWallis4220-Apr-13 2:46
memberJohnWallis4220-Apr-13 2:46 
GeneralRe: comparing to ttmath - not confirmed Pin
Karl Runmo20-Apr-13 21:30
memberKarl Runmo20-Apr-13 21:30 
GeneralRe: comparing to ttmath - not confirmed Pin
JohnWallis4221-Apr-13 3:02
memberJohnWallis4221-Apr-13 3:02 
GeneralRe: comparing to ttmath - not confirmed Pin
Karl Runmo21-Apr-13 7:39
memberKarl Runmo21-Apr-13 7:39 
GeneralRe: comparing to ttmath - not confirmed Pin
JohnWallis4222-Apr-13 2:17
memberJohnWallis4222-Apr-13 2:17 
GeneralRe: comparing to ttmath - not confirmed Pin
Karl Runmo22-Apr-13 3:13
memberKarl Runmo22-Apr-13 3:13 
GeneralRe: comparing to ttmath - not confirmed Pin
JohnWallis4222-Apr-13 18:08
memberJohnWallis4222-Apr-13 18:08 
GeneralRe: comparing to ttmath - not confirmed Pin
Karl Runmo22-Apr-13 21:11
memberKarl Runmo22-Apr-13 21:11 
GeneralRe: comparing to ttmath - not confirmed Pin
JohnWallis4223-Apr-13 2:22
memberJohnWallis4223-Apr-13 2:22 
GeneralRe: comparing to ttmath - not confirmed Pin
Karl Runmo24-Apr-13 11:44
memberKarl Runmo24-Apr-13 11:44 
GeneralRe: comparing to ttmath - not confirmed Pin
JohnWallis4224-Apr-13 14:24
memberJohnWallis4224-Apr-13 14:24 
GeneralRe: comparing to ttmath - not confirmed Pin
JohnWallis4224-Apr-13 17:07
memberJohnWallis4224-Apr-13 17:07 
GeneralRe: comparing to ttmath - not confirmed Pin
JackDingler24-Apr-13 10:35
memberJackDingler24-Apr-13 10:35 
GeneralRe: comparing to ttmath - not confirmed Pin
Karl Runmo24-Apr-13 11:49
memberKarl Runmo24-Apr-13 11:49 
GeneralRe: comparing to ttmath - not confirmed Pin
Karl Runmo21-Apr-13 11:32
memberKarl Runmo21-Apr-13 11:32 
GeneralRe: comparing to ttmath - not confirmed Pin
Tomasz Sowa21-Apr-13 18:49
professionalTomasz Sowa21-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.



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.

If you want to compare (for speed) two libraries or programs first you should check what algorithms they used especially their computational complexity:[^]

Your library for multiplication uses such a code:


		pResValues[a+b] += m_pValues[a]*A.m_pValues[b];

This is the schoolbook algorithm with O(n^2). TTmath for small vectors is using it too but for larger vectors uses Karatsuba multiplication which has O( n^(ln(3)/ln(2) ) :[^]

So your library will never be as fast as ttmath, especially if you'll get more digits to multiply. You can make a test by yourself, try changing DIGITS to:
#define DIGITS 10000
You have to change KRFLOAT_ENTRIES as well:
#define KRFLOAT_ENTRIES 3000
and for ttmath you can set 66560 bits mantissa (this stores more that 20000 decimal digits):

and you'll see that the ttmath's karatsuba multiplication outperforms your schoolbook multiplication (even where in such a case ttmath is using two times larger mantissa).

But the problem is when you really need a mantissa of variable size. In ttmath you can define some temporary objects, e.g.:
ttmath::Big<1, 10> 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):[^]

and mpfr:[^]

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):[^]
GeneralRe: comparing to ttmath - not confirmed Pin
Karl Runmo22-Apr-13 0:55
memberKarl Runmo22-Apr-13 0:55 
QuestionHave you looked at boost multiprecision Pin
John Bandela18-Apr-13 8:12
memberJohn Bandela18-Apr-13 8:12 
AnswerRe: Have you looked at boost multiprecision Pin
Karl Runmo18-Apr-13 21:59
memberKarl Runmo18-Apr-13 21:59 
GeneralRe: Have you looked at boost multiprecision Pin
John Bandela19-Apr-13 10:56
memberJohn Bandela19-Apr-13 10:56 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

Permalink | Advertise | Privacy | Terms of Use | Mobile
Web02-2016 | 2.8.180318.3 | Last Updated 22 Apr 2013
Article Copyright 2013 by Karl Runmo
Everything else Copyright © CodeProject, 1999-2018
Layout: fixed | fluid