Category Archives: approximation

Bitcoin inflation

bitcoinaltera
Bitcoins are created through reward for successfully mining a block. The current reward as of writing is 12.5 BTC per block.

Referring to the bitcoin history, the current bitcoin in circulation is around 16,378,375, and a year ago it was 15,628,475. So there is 749,900 bitcoins being mined in between.

The rate of a successful mining is around 10 minutes. Assuming this, in one year there should be 24 * 60 / 10 * 12.5 * 365 bitcoins created. That is 657,000 and this theoretical value doesn’t quite add up with the history as this only amounts to 87.6% to the historic value. Close, but more than 10% than expected.

It turns out, in fact, there is a mechanism built-in to the bitcoin to halve the reward as a form of inflation. A month from now will mark the anniversary for the last Bitcoin reward halving from 25 BTC to 12.5 BTC. This change is by design and happened twice as expected in the past, from 50 to 25, to 12.5 as of time of writing.

The first block receiving 12.5 BTC is 420,000 on 2016-07-09, according to the original constant set in stone by the creator of Bitcoin:

Consensus.nSubsidyHalvingInterval = 210000;

Therefore during the period mentioned above where 749,900 are mined there are times when the reward was 25 and some other 12.5.

A rough calculation shown the current reward, which is 12.5 BTC per block, applies to 334 days during that 365-day period. Revising the calculation of the theoretical value resulted in 712,800 bitcoins. Taking into account this fact the estimation improved from 88% to 95% of historical values.

Advertisements

Implementing parallel GPU function in CUDA for R

There are existing R packages for CUDA. But if there is a need to customize your own parallel code on NVIDIA GPU to be called from R, it is possible to do so with the CUDA Toolkit. This post demonstrates a sample function to approximate the value of Pi using Monte Carlo method which is accelerated by GPU. The sample is built using Visual Studio 2010 but the Toolkit is supported on linux platforms as well. It is assumed that the Visual Studio is integrated with the CUDA Toolkit.

The first thing to do is to create a New Project using the Win32 Console Application template, and specify DLL with Empty project option.

RCuda1
RCuda2

And then, some standard project environment customization including:

CUDA Build Customization:
RCuda3

CUDA Runtime, select Shared/dynamic CUDA runtime library:
RCuda5

Project Dependencies setting. Since the CUDA code in this example utilize curand for Monte Carlo, the corresponding library must be included or else the linking will fail.
RCuda4

Finally the time to code. Only a cu file is needed which resembles the standard directives. It is important to include the extern declaration as below for R to call.
RCuda6

After a successful compile, the DLL will be created with the CUDA code. This DLL will be registered in R for calling.
RCuda7RCuda8

Finally, start R and issue the dyn.load command to load the DLL into the running environment. Shown below is a “wrapper” R function to make calling the CUDA code easier. Notice at the heart of this wrapper is the .C function.
RCuda9

Last but not least, the CUDA Toolkit comes with a visual profiler which is capable to be launched for profiling the performance of the NVIDIA GPU. It can be launched from the GUI, or using a command line like the example below. It should be noted that the command line profiler must be started before R or it might not be able to profile properly.RCuda11

The GUI profiler is equipped with a nice interface to show performance statistics.RCuda10

Chebyshev approximation of normal distribution probability

Apart from the approximation method by means of the Taylor function, another numerical technique which is considered by most as the de facto method is the Chebyshev approximation. In TI Nspire, the calculation can be done as below. The piece-wise function helps to decide the result from whether d is positive. For better performance, some constants can be pre-calculated instead of as shown below, like the square root of double π. Intensive calculations definitely will benefit from pre-calculated values.

ChebyshevApprox