Re: [ANN] lua-bint - Arbitrary precision integer arithmetic library in pure Lua
[
Date Prev][
Date Next][
Thread Prev][
Thread Next]
[
Date Index]
[
Thread Index]
- Subject: Re: [ANN] lua-bint - Arbitrary precision integer arithmetic library in pure Lua
- From: Sean Conner <sean@...>
- Date: 2020年7月10日 19:57:18 -0400
It was thus said that the Great Sean Conner once stated:
>
> You want to as large of a division as possible. On a 32-bit system, you
> want to do a "64 bits divided by 32 bits" repeatedly, and on a 64-bit
> system, you'll want to do a "128 bits divided by 64 bits" repeatedly [1].
> For best results, you would need to hit assembly, but a reasonable C
> compiler will probably produce decent results with code like:
Please note that to do such divisions, the data needs to be correctly
adjusted for the endianness of the system. For my sample code here:
> #include <stdio.h>
> #include <stdlib.h>
> #include <string.h>
> #include <limits.h>
> #include <assert.h>
>
> #define MAX 256
>
> unsigned long xremainder(
> unsigned long dest[MAX],
> unsigned long const src[MAX],
> unsigned long demon
> )
> {
> unsigned long long carry = 0;
> unsigned long long quo;
> unsigned long long rem;
> size_t i;
>
> for (i = 0 ; i < MAX ; i++)
> {
> carry <<= (sizeof(long) * CHAR_BIT);
> carry |= src[i];
> quo = carry / demon;
> rem = carry % demon;
> dest[i] = quo;
> carry = rem;
> }
>
> return rem;
> }
>
> int main(void)
> {
> unsigned long src[MAX];
> unsigned long dest[MAX];
> unsigned long zero[MAX];
> char buffer[BUFSIZ];
> char *p;
>
> assert(sizeof(unsigned long long) > sizeof(unsigned long));
>
> memset(zero, 0,sizeof(zero));
> memset(src, 255,sizeof(src)); /* maximum number */
>
> p = &buffer[BUFSIZ];
> *--p = '0円';
>
> do
> {
> unsigned long rem = xremainder(dest,src,10);
> assert(rem <= 9);
> *--p = rem + '0';
> memcpy(src,dest,sizeof(src));
> } while(memcmp(src,zero,sizeof(zero)));
>
> puts(p);
> return 0;
> }
I treat the array as a big-endian system, but on an x86 system, each
unsigned long in the array is stored little-endian. Just be aware of this
when doing the math.
-spc (Just thought I should mention this)