Decimal arithmetic

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

I've been asked off-list by a former member about digit
extraction  
functions in GMP. I've given the usual lecture about how
digit  
extraction is a slow operation if the library does binary
arithmetic,  
since it requires a base-2 to base-10 conversion. With that
said, a  
base-10 library would provide efficient digit extraction
while not  
sacrificing much performance.

So what are the choices of libraries that support base-10
arithmetic?  
Can GMP itself be easily modified to support it? As far as I
know, Pi- 
calculating programs such as QuickPi and PiFast do the
arithmetic in  
decimal since the result will be eventually printed out (in
decimal,  
of course). But these programs are generally closed-source,
and even  
if they weren't, I assume they wouldn't provide a proper
library  
interface.

Décio
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.5 (Darwin)

iD8DBQFGE9ZY9zcAVrR+ETURAhHxAJ9dPaSIA0MseMvEx1tZ/YqY2mfu+ACf
a5/X
I3SI2IBycHQZWc4qKUJP0i0=
=3IgD
-----END PGP SIGNATURE-----
_______________________________________________
gmp-discuss mailing list
gmp-discussswox.com
http://s
wox.com/mailman/listinfo/gmp-discuss

On Wed, Apr 04, 2007 at 01:46:13PM -0300, Décio Luiz Gazzoni
Filho wrote:
> 
> I've been asked off-list by a former member about digit
extraction  
> functions in GMP. I've given the usual lecture about
how digit  
> extraction is a slow operation if the library does
binary arithmetic,  
> since it requires a base-2 to base-10 conversion. With
that said, a  
> base-10 library would provide efficient digit
extraction while not  
> sacrificing much performance.
> 
> So what are the choices of libraries that support
base-10 arithmetic?  

FWIW, some history of base-10:
-- IBM mainframes have supported base-10 arithmetic since
the 1960's.
   This was primarily to support accounting, in order to
make life
   easier for banks and utilities and anyone who sent out
zillions
   of invoices every month.

-- This base-10 arith has been backwards-compat supported
all those
   decades, and is now making its debut on a modern CPU, the
Power6
   due to ship "any day now". As a result, base-10
arithmetic support
   was proposed to ANSI as a libc or libm math standard, and
I beleive
   the standard was recently (last year or two) accepted.

-- I don't beleive that it is widely supported in general.
The only
   hardware support will be on power6, so I don't see much
point in 
   doing base-10 aritmetic on anything other than that. 

> Décio

Unless, of course, this is another one of those
"poisson d'avril" 
emails.

_______________________________________________
gmp-discuss mailing list
gmp-discussswox.com
http://s
wox.com/mailman/listinfo/gmp-discuss

On Wed, 2007-04-04 at 18:31, Linas Vepstas wrote:

> FWIW, some history of base-10:
> -- IBM mainframes have supported base-10 arithmetic
since the 1960's.
>    This was primarily to support accounting, in order
to make life
>    easier for banks and utilities and anyone who sent
out zillions
>    of invoices every month.
> 
> -- This base-10 arith has been backwards-compat
supported all those
>    decades, and is now making its debut on a modern
CPU, the Power6
>    due to ship "any day now". As a result,
base-10 arithmetic support
>    was proposed to ANSI as a libc or libm math
standard, and I beleive
>    the standard was recently (last year or two)
accepted.
> 
> -- I don't beleive that it is widely supported in
general. The only
>    hardware support will be on power6, so I don't see
much point in 
>    doing base-10 aritmetic on anything other than that.


I was doing decimal arithmetic on a Z80 in assembly language
over 25
years ago.  Some skillful use of Google will unearth
supporting evidence
for this claim. (Further hints on request.)

As far as I know the Z80 is still in widespread use though,
I concede,
very rarely as a compute engine these days.


Paul


_______________________________________________
gmp-discuss mailing list
gmp-discussswox.com
http://s
wox.com/mailman/listinfo/gmp-discuss

> I've been asked off-list by a former member about digit
extraction  
> functions in GMP. I've given the usual lecture about
how digit  
> extraction is a slow operation if the library does
binary arithmetic,  
> since it requires a base-2 to base-10 conversion. With
that said, a  
> base-10 library would provide efficient digit
extraction while not  
> sacrificing much performance.
>
> So what are the choices of libraries that support
base-10 arithmetic?  
> Can GMP itself be easily modified to support it? As far
as I know, Pi- 
> calculating programs such as QuickPi and PiFast do the
arithmetic in  
> decimal since the result will be eventually printed out
(in decimal,  
> of course). But these programs are generally
closed-source, and even  
> if they weren't, I assume they wouldn't provide a
proper library  
> interface.

Base-2 to base-10 conversion costs O(M(n) log(n)) for n-bits
numbers,
where M(n) denotes the multiplication cost. There is indeed
a log(n)
overhead, but most computations are much more expensive. If
you implement
arithmetic in radix 10, you will loose a constant factor on
your ***whole***
computation, which will kill the small speedup on the base
conversion.
Thus my personal point of view is that it is better to
compute in radix 2
as GMP does. Of course this assumes the base conversion
really has complexity
O(M(n) log(n)), which is not completely true with gmp-4.2.1:
the base-2 to
base-10 conversion implements a subquadratic algorithm, but
relies on the
division, which has cost O(M(n) log(n)) in 4.2.1 instead of
O(M(n)) in 5.0.
Thus the current base 2 -> base 10 conversion has cost
O(M(n) log(n)^2).

Paul
_______________________________________________
gmp-discuss mailing list
gmp-discussswox.com
http://s
wox.com/mailman/listinfo/gmp-discuss