13,595,207 members
alternative version

#### Stats

28.8K views
14 bookmarked
Posted 15 Apr 2013
Licenced CPOL

# 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
 It's the other running threads your not measuring. So. My impression is your running the program, in a multitasking environment, along with other programs. The time and cpu usage of other programs, mouse detection, timer update, window repaint, etc, along with other programs such as Ages of Empires are hard to predict. In Linux when you ask for times it will give you 3 back! program time, real time and another time. Hence, if you turn off all the games, and very carefully, in a special sequence, turn off many off the background "windows"-tasks [you won't be able to shutdown, switch user, etc normally after - but reboot restores all], if you do all that: you lowest program time will improve. To save you all that trouble: run each program 10^6 times (enough to smooth out outliers) and compare the averages, sigmas and standard deviations. Plot them, Note the machine make, model, OS build, CPU(+MHz)[make,build], (+ anything [chips] that could be considered different of your machine). Try a DOS only boot. - and turn off your internet, unplug all usbs AND no mouse.
 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
 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: 22-Jun-18 2:22 Refresh 12 Next »