lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index]


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)