Implementing BigDecimal in K

bigK.md

Implementing BigDecimal in K

The largest numeric types K has available are 64-bit integer and floating point numbers. To solve the constant holes requiring 1000 decimal digits of precision, you'll have to implement arithmetic operations with higher precision.

Number representation

The first choice to make is how to represent precise numbers. Using a list of base 10 digits makes printing the numbers convenient. In the following, we use a single digit for the integer part (can be any integer) and 1000 digits (0-9) for the decimal part.

ONE: ~!1001   / 1.0 = 1 0 0 0 ...

`0:"1.",/$1_ONE / prints 1.0000...

Carry

Multiple arithmetic operations require running a carry operation, we'll define this separately and run it after the other operation. Carry needs to start at the least significant digit (right) and move towards the integer part (left). This can be implemented using a scan on the reversed list:

car: {10 0[ONE]!'|0{y+-10!x}\|x}

car[-3 12 34 3]  / -2 5 4 3

The 10 0[ONE]!' takes the digits in the decimal part modulo 10 and keeps the integer digit.

Addition/subtraction

Since arithmetic operators work element-wise on lists in K, + and - just need a carry to perform addition and subtraction on two big numbers:

add: car@+
sub: car@-

add[0 9 7 5;1 2 8 0]  / 0.975+1.280 = 2 2 5 5
sub[0 9 7 5;1 2 8 0]  / 0.975-1.280 =-1 6 9 5

If you want to add a small number to a big one, either convert it to a big one with ONE*x, or find a way to just add it to the first element.

Division

Dividing a big number by a small integer can be done using long division:

div: {(-y)!0{z+10*x!y}[y]\x}

div[1 0 0 0;3]  / 1%3 = 0 3 3 3

If you need to divide one big number by another, I'd recommend trying to find a different algorithm to solve the hole. If you really want to do this, try to implement http://www.numberworld.org/y-cruncher/internals/division.html.

Multiplication

Multiplying a big number by a small integer is just car@*, multiplying two big ones requires long multiplication

mul: {car@+/'(,\y)*|',\x}

Note that this only computes as many digits as the inputs have, so it loses some precision. In practice you might need to make your numbers a few digits longer to get precise enough results.

mul[1 2 5 0;0 6 6 6]  / 1.25 * 0.666 ~= 0 8 2 8
mul[1 2 5 0 0 0;0 6 6 6 0 0] / 1.25 * 0.666 = 0 8 3 2 5 0

Golfing opportunities

• If you just work with numbers in [0,1), getting rid of the integer part simplifies a few things.
• You don't need to use carry after every operation, often a single time in the entire calculation suffices.
• There is a shorter implementation of the carry using floating point numbers, that is precise enough in some cases.