[Dlang-internal] I need cent and ucent to be implemented soon

[Elmar]

On Sunday, 18 April 2021 at 23:31:12 UTC, Elmar wrote:
> On Wednesday, 18 September 2019 at 18:42:32 UTC, Joseph Rushton 
> Wakeling wrote:
>> On Saturday, 4 May 2019 at 19:08:10 UTC, Murilo wrote:
>>> BigInt takes too long. I need something as fast as the 
>>> primitive types.
>>
>> What hardware are you planning on running your programs on? 
>> I'm not sure how good a speed you can guarantee without native 
>> hardware support.
>
> Hello together.
> ...

I'm sorry for double post, have to correct something but don't 
know how to edit posts.

I was wrong with the number of atoms in the universe. `2^128` is 
close to `10^(128/3) < 10^43` which is about the root of the 
assumed estimation of the number of atoms in universe. But 
128-bit numbers are still extremely large as a count value, 
exceeding any common-day numbers, common numbers in electronics 
or software. You rarely need 128-bit numbers as single count 
values (so in practice they are used for SIMD where 
medium-accurate sensors deliver 16-bit sensor samples), probably 
you could fit any counting value that practically can be found in 
our universe into a 256-bit number.

And for the division: the idea is based on the finding that you 
can calculate the division with arbitrary precision via a 
recursive formula, using floor and the remainder. Applying the 
recursion until no result bit (in the limited precision) changes 
anymore has a bad performance in the worst case (using one big 
multiplication per result bit).

But looking at the pattern behind the multiplication (recursion), 
needed to calculate the inverse, it's easy to see, that the 
multiplicative inverse just is `1/b = x * 0.111111..._(2^n/y) = 
0.1111..._(b+1)` where 0.1111... (equal to `1 / (r - 1)` in any 
number system to the base `r > 1`) is a periodic number (or 
polynomial) with the radix `2^n/y` (very likely a rational 
number), `x = floor(2^n / b)` and `y = 2^n % b`. Numbers are just 
used as convenient representation of polynomials.

While my first shown division approach calculates this specific 
number with one digit per cycle, the efficient approach 
afterwards doubles the number of calculated 1-digits for each 
cycle. Anyone who can calculate more digits per cycle with same 
complexity would become famous.