[Dlang-internal] I need cent and ucent to be implemented soon
Elmar
chrehme at gmx.de
Tue Apr 27 18:00:09 UTC 2021
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.
More information about the Dlang-internal
mailing list