Large numbers (or is Ada the choice for me?)

Large numbers (or is Ada the choice for me?)

[Hans Georg Schaathun]

I need a tool to solve large systems of linear equations, with no
floating point operations (or any other approximations) allowed.
Even though I am not a seasoned programmer, I think I'll have to
write the tool myself.

My question is, will it be reasonably simple to handle large
rational numbers with Ada?  Is there any packages for this?

Does basic Ada (gnat) support (f.ex.) 2048-bit integers?  Does
any module exist for integers of dynamic size?  Are these
handled reasonably efficiently, or is there much overhead?

I guess I will manage to implement the rational numbers without
too much hardship, but I really don't feel like implementing
arithmetics on large integers.

:-- Hans Georg
-- 
Signature en panne.

Re: Large numbers (or is Ada the choice for me?)

[Marin David Condic]

"Hans Georg Schaathun" <georg@ii.uib.no> wrote in message
news:slrn9ai9uk.iv9.georg@apal.ii.uib.no...
> I need a tool to solve large systems of linear equations, with no
> floating point operations (or any other approximations) allowed.
> Even though I am not a seasoned programmer, I think I'll have to
> write the tool myself.
>
This is a hopeless mission. Consider the instant you're row reduction
results in 1/3 - can you put that into a computer *without* an approximation
and still do math on it? The only issue then is how much accuracy is enough?

There are some Ada packages out there to do matrix math, but none that I
know of that will do so without some version of floating point numbers.
However, you could use these packages as models for ones of your own
implementation.

A good place to start looking for Ada software is: http://www.adapower.org/
A quick Google search with the words "Ada Linear Algebra" yielded:
http://www.cc.utah.edu/~nahaj/ada/math/linear.ads.html
http://www.masstech.com/mpdesc.htm

See also:
http://lglwww.epfl.ch/Team/MW/mw_components.html

As I recall Mats Weber had some Linear Algebra stuff in Ada...


> My question is, will it be reasonably simple to handle large
> rational numbers with Ada?  Is there any packages for this?
>
easier than in most languages because you can create a package to house the
whole thing and use it just as if it was a native data type. Ex:

package My_Big_Numbers is
    type Really_Big_Number_Type is private ;
    function "+" (
        Left, Right : in Really_Big_Number_Type)
            return Really_Big_Number_Type ;
    --  And so on....

I know of none in existence, but that doesn't mean there isn't one. Try
Adapower &/or Google.

A quick search of Google using "Big Number Arithmetic Ada" gave me:

http://www.chez.com/bignumber/

> Does basic Ada (gnat) support (f.ex.) 2048-bit integers?  Does
> any module exist for integers of dynamic size?  Are these
> handled reasonably efficiently, or is there much overhead?
>
Nope. Nope and Not Applicable. You're either going to have to download
someone's large-number-package(s) or roll your own. I know of no general
purpose languages that are going to give you math on that big a scale right
out of the box. It should not be too hard to make your own code and it might
make a valuable contribution if you were to post it somewhere...


> I guess I will manage to implement the rational numbers without
> too much hardship, but I really don't feel like implementing
> arithmetics on large integers.
>
Someone probably has done this, but it would be nice if you end up creating
one to post it somewhere useful.

MDC
--
Marin David Condic
Senior Software Engineer
Pace Micro Technology Americas    www.pacemicro.com
Enabling the digital revolution
e-Mail:    marin.condic@pacemicro.com
Web:      http://www.mcondic.com/

Re: Large numbers (or is Ada the choice for me?)

[Brian Catlin]

Try the Big Numbers Page:  http://www.chez.com/bignumber/index.html

 -Brian

"Hans Georg Schaathun" <georg@ii.uib.no> wrote in message
news:slrn9ai9uk.iv9.georg@apal.ii.uib.no...
> I need a tool to solve large systems of linear equations, with no
> floating point operations (or any other approximations) allowed.
> Even though I am not a seasoned programmer, I think I'll have to
> write the tool myself.
>
> My question is, will it be reasonably simple to handle large
> rational numbers with Ada?  Is there any packages for this?
>
> Does basic Ada (gnat) support (f.ex.) 2048-bit integers?  Does
> any module exist for integers of dynamic size?  Are these
> handled reasonably efficiently, or is there much overhead?
>
> I guess I will manage to implement the rational numbers without
> too much hardship, but I really don't feel like implementing
> arithmetics on large integers.
>
> :-- Hans Georg
> --
> Signature en panne.

Re: Large numbers (or is Ada the choice for me?)

[David Starner]

On Fri, 9 Mar 2001 14:35:42 -0500, Marin David Condic <marin.condic.auntie.spam@pacemicro.com> wrote:
>"Hans Georg Schaathun" <georg@ii.uib.no> wrote in message
>news:slrn9ai9uk.iv9.georg@apal.ii.uib.no...
>> I need a tool to solve large systems of linear equations, with no
>> floating point operations (or any other approximations) allowed.
>> Even though I am not a seasoned programmer, I think I'll have to
>> write the tool myself.
>>
>This is a hopeless mission. Consider the instant you're row reduction
>results in 1/3 - can you put that into a computer *without* an approximation
>and still do math on it? The only issue then is how much accuracy is enough?

Yes. Computers can handle fractions just fine with the appropriate 
package. I'm not sure it's feasible to have no approximations in a large
system of linear equations, but it's possible.

>A good place to start looking for Ada software is: http://www.adapower.org/
>A quick Google search with the words "Ada Linear Algebra" yielded:
>http://www.cc.utah.edu/~nahaj/ada/math/linear.ads.html
>http://www.masstech.com/mpdesc.htm
>
>See also:
>http://lglwww.epfl.ch/Team/MW/mw_components.html
>
>As I recall Mats Weber had some Linear Algebra stuff in Ada...

He also has a big number package. If efficency is key, I might look
at the binding to gmp (http://www.ii.uib.no/~gisle/adagmp/).

>easier than in most languages because you can create a package to house the
>whole thing and use it just as if it was a native data type. 

Not easier than any other language with operator overloading and packages.
(C++ would be significantly easier, as Ada won't let you make a type
that "looks like" an integer.)

>Nope. Nope and Not Applicable. You're either going to have to download
>someone's large-number-package(s) or roll your own. I know of no general
>purpose languages that are going to give you math on that big a scale right
>out of the box. 

Common Lisp would give you the rationals and the big numbers out of
the box. 

-- 
David Starner - dstarner98@aasaa.ofe.org
Pointless website: http://dvdeug.dhis.org
"I don't care if Bill personally has my name and reads my email and 
laughs at me. In fact, I'd be rather honored." - Joseph_Greg

Re: Large numbers (or is Ada the choice for me?)

[Randy Brukardt]

Marin David Condic wrote in message <98bbbg$jmf$1@nh.pace.co.uk>...
>"Hans Georg Schaathun" <georg@ii.uib.no> wrote in message
>news:slrn9ai9uk.iv9.georg@apal.ii.uib.no...
>I know of none in existence, but that doesn't mean there isn't one. Try
>Adapower &/or Google.

Every Ada compiler has a (nearly) infinite precision math package
built-in. That's because of the requirements of the ACATS on literals:

    3#0.1# /= 0.333333333333333333333333333333333333333333333333

And if there is any rounding, you'll fail this test.

But those packages are part of the compiler, not something usually
available to the public. The one in Janus/Ada is full of assembler and
weird usage rules (the latter because it was written in Ada 83, and we
didn't have controlled types to do the cleanup). The guy who wrote it
for use created a cute little calculator using it, and included some
scripts to calculate PI to 1000 digits and other useless tasks... :-)

                Randy.

Re: Large numbers (or is Ada the choice for me?)

[JP Thornley]

In article <slrn9ai9uk.iv9.georg@apal.ii.uib.no>, Hans Georg Schaathun
<georg@ii.uib.no> writes
>My question is, will it be reasonably simple to handle large
>rational numbers with Ada?  Is there any packages for this?

I've collected several 'big integer' and rational number packages off
the web (I don't still have the URLs but here are the names of the zip
files and the contact details for the authors from their documentation,
so your favourite search engine should find them):
   Unlimit8 from Dimitriy Anisimkov (anisimkov@yahoo.com)
   Multi002 from Gautier.deMontmollin@Maths.UniNe.CH
   Big_0_06 from Jerome Delcourt (sikander@club-internet.fr)
   AdaGMP from Gisle Saelensminde (gisle@ii.uib.no)

Having collected then I've never had the time to do anything with them
so can't pass any opinions.

(I also have an unbounded rational number package of my own that I wrote
as an exercise, which you are welcome to have - just ask - it is still
in Ada 83.)

Cheers,

Phil

-- 
JP Thornley

Re: Large numbers (or is Ada the choice for me?)

[Tucker Taft]

Hans Georg Schaathun wrote:
> 
> I need a tool to solve large systems of linear equations, with no
> floating point operations (or any other approximations) allowed.
> Even though I am not a seasoned programmer, I think I'll have to
> write the tool myself.
> 
> My question is, will it be reasonably simple to handle large
> rational numbers with Ada?  Is there any packages for this?
> 
> Does basic Ada (gnat) support (f.ex.) 2048-bit integers?  Does
> any module exist for integers of dynamic size?  Are these
> handled reasonably efficiently, or is there much overhead?

The source for the GNAT compiler includes the source for
their "universal arithmetic" package I presume, which (again,
presumably) does arbitrary precision integer and rational 
arithmetic.

> 
> I guess I will manage to implement the rational numbers without
> too much hardship, but I really don't feel like implementing
> arithmetics on large integers.

Try the GNAT compiler sources.  We also have one lying around somewhere.

My friends in "experimental mathematics" (sounds like fun, eh?) generally
prefer to use arbitrary-precision packages based on the Chinese
remainder theorem, because that allows large multiplications to
be performed very efficiently.  Essentially a number is represented
by its value modulo a series of prime numbers, typically those just
less than 2**31.  Multiplication can then be done by 
multiplying the individual "digits" independently.  A few dozen "digits"
is usually enough to handle some very large numbers. 
 
> 
> :-- Hans Georg
> --
> Signature en panne.

-- 
-Tucker Taft   stt@avercom.net   http://www.averstar.com/~stt/
Chief Technology Officer, AverCom Corporation (A Titan Company) 
Burlington, MA  USA (AverCom was formerly the Commercial Division of AverStar:
http://www.averstar.com/services/ebusiness_applications.html)

Re: Large numbers (or is Ada the choice for me?)

[Robert A Duff]

"Marin David Condic" <marin.condic.auntie.spam@pacemicro.com> writes:

> This is a hopeless mission. Consider the instant you're row reduction
> results in 1/3 - can you put that into a computer *without* an approximation
> and still do math on it?

Yes.  What's the problem?  A rational arithmetic package can do exact
arithmetic on 1/3 or any other rational number you can name.

>...I know of no general
> purpose languages that are going to give you math on that big a scale right
> out of the box.

Lisp.  Smalltalk.  &c.

- Bob

Re: Large numbers (or is Ada the choice for me?)

[Marin David Condic]

"David Starner" <dvdeug@x8b4e53cd.dhcp.okstate.edu> wrote in message
news:98bfb2$a2g1@news.cis.okstate.edu...
> Yes. Computers can handle fractions just fine with the appropriate
> package. I'm not sure it's feasible to have no approximations in a large
> system of linear equations, but it's possible.
>
Maybe a bad example - my point is that there exists a possibility of
generating numbers which are going to have an infinite number of decimal
places and memory only goes so far. Hence, you're going to need some sort of
approximation. Picking a rather large upper limit for that approximation is
probably good enough.

For matrix stuff, you might theoretically be able to handle the math
entirely in fractions, but would you like the solution in our lifetime? :-)
(Simulated big number math is probably bad enough!)

MDC
--
Marin David Condic
Senior Software Engineer
Pace Micro Technology Americas    www.pacemicro.com
Enabling the digital revolution
e-Mail:    marin.condic@pacemicro.com
Web:      http://www.mcondic.com/

Re: Large numbers (or is Ada the choice for me?)

[Marin David Condic]

"Robert A Duff" <bobduff@world.std.com> wrote in message
news:wcck85yeeat.fsf@world.std.com...
> "Marin David Condic" <marin.condic.auntie.spam@pacemicro.com> writes:
>
> > This is a hopeless mission. Consider the instant you're row reduction
> > results in 1/3 - can you put that into a computer *without* an
approximation
> > and still do math on it?
>
> Yes.  What's the problem?  A rational arithmetic package can do exact
> arithmetic on 1/3 or any other rational number you can name.
>
Well, let me check a few assumptions. 1) We can never run out of numbers.
(Go ahead. Use all you want. We'll make more! :-) 2) We *can* and *will*
eventually run out of memory. Hence, even if you did all the math with some
sort of fractional representation rather than a decimal representation, it
would be possible to construct numbers that exceed the capacity of the
machine. Hence, I think it stands to reason that you would be off on a
fool's errand to insist on no approximations or limitations whatsoever.
There has to be some sort of practical upper limit imposed by the available
memory if nothing else.

As I said elsewhere, I rather hastily picked a bad example - but I think the
point still stands that one will have to live with some sort of
approximation on the representation - even if in practice, it may be so
small as to not matter. (Until you intersect Chaos Theory, at least! :-)

MDC

Re: Large numbers (or is Ada the choice for me?)

[Keith Thompson]

georg@ii.uib.no (Hans Georg Schaathun) writes:
> I need a tool to solve large systems of linear equations, with no
> floating point operations (or any other approximations) allowed.
> Even though I am not a seasoned programmer, I think I'll have to
> write the tool myself.
> 
> My question is, will it be reasonably simple to handle large
> rational numbers with Ada?  Is there any packages for this?
> 
> Does basic Ada (gnat) support (f.ex.) 2048-bit integers?  Does
> any module exist for integers of dynamic size?  Are these
> handled reasonably efficiently, or is there much overhead?
> 
> I guess I will manage to implement the rational numbers without
> too much hardship, but I really don't feel like implementing
> arithmetics on large integers.

I believe Gnat includes an arbitrary-precision rational number
package; it needs it at compilation time to handle the rather
stringent language rules for compile-time expressions.

For a good time, try compiling

    Kaboom : constant := (1.0 + 1.0e-10) ** 1.0e10;

The result should be a good approximation to e, but the compiler's
front end will almost certainly run out of memory trying to evaluate
the expression.  Don't try this if your operating doesn't cope well
with memory hogs.  If your own application does this kind of thing,
either in general or only for certain matrices, you may be in trouble.

Anyway, since Gnat is GPL'ed, you can grab pieces of it and use them
in your own code (with the usual restrictions).  It may even provide
the package as part of the runtime library.  Look for something like
"Universal_Arithmetic".

... Ah, found it.  See packages Uintp (universal integer arithmetic)
and Urealp (universal real arithmetic).  Figuring out how to use them
is left as an exercise.

-- 
Keith Thompson (The_Other_Keith) kst@cts.com  <http://www.ghoti.net/~kst>
San Diego Supercomputer Center           <*>  <http://www.sdsc.edu/~kst>
MAKE MONEY FAST!!  DON'T FEED IT!!

Re: Large numbers (or is Ada the choice for me?)

[David Starner]

On Fri, 9 Mar 2001 18:12:56 -0500, Marin David Condic <marin.condic.auntie.spam@pacemicro.com> wrote:
>"David Starner" <dvdeug@x8b4e53cd.dhcp.okstate.edu> wrote in message
>news:98bfb2$a2g1@news.cis.okstate.edu...
>> Yes. Computers can handle fractions just fine with the appropriate
>> package. I'm not sure it's feasible to have no approximations in a large
>> system of linear equations, but it's possible.
>>
>Maybe a bad example - my point is that there exists a possibility of
>generating numbers which are going to have an infinite number of decimal
>places and memory only goes so far. Hence, you're going to need some sort of
>approximation.

No, not if you want to expand the complexity. Every irrational number you 
would probably need you could express in terms of pi, e, sqrt, cube roots,
sin, and rational numbers.

>For matrix stuff, you might theoretically be able to handle the math
>entirely in fractions, but would you like the solution in our lifetime? :-)
>(Simulated big number math is probably bad enough!)

Depending on what you're doing, it may be fast enough. My question is
where do you prefer 12038838484884757761111111111456646243627 /
12883848484058534671734792837598275927 to the equivelent decimal 
solution.

-- 
David Starner - dstarner98@aasaa.ofe.org
Pointless website: http://dvdeug.dhis.org
"I don't care if Bill personally has my name and reads my email and 
laughs at me. In fact, I'd be rather honored." - Joseph_Greg

Re: Large numbers (or is Ada the choice for me?)

[tmoran]

>For matrix stuff, you might theoretically be able to handle the math
>entirely in fractions, but would you like the solution in our lifetime? :-)
  An extremely long time ago I did a polynomial arithmetic package
explicitly for getting algebraic solutions of matrix inversions.
I recall inverting a matrix sounded like a bottle being filled with
water on the speaker hooked to the CDC1604.  And machines today are
even faster.  ;)

Re: Large numbers (or is Ada the choice for me?)

[Florian Weimer]

dvdeug@x8b4e53cd.dhcp.okstate.edu (David Starner) writes:

> >Maybe a bad example - my point is that there exists a possibility of
> >generating numbers which are going to have an infinite number of decimal
> >places and memory only goes so far. Hence, you're going to need some sort of
> >approximation.
> 
> No, not if you want to expand the complexity. Every irrational number you 
> would probably need you could express in terms of pi, e, sqrt, cube roots,
> sin, and rational numbers.

It's true that most linear algebra problems can be expressed in
algebraic field extensions of, say, Q(pi, e), but there are some whose
solutions cannot be represented even by nested roots (for example,
eigenvalue problems).

Re: Large numbers (or is Ada the choice for me?)

[Jeffrey Carter]

Marin David Condic wrote:
> 
> There are some Ada packages out there to do matrix math, but none that I
> know of that will do so without some version of floating point numbers.
> However, you could use these packages as models for ones of your own
> implementation.

The PragmAda Reusable Components' matrix implementation imports its
element type. This allows matrices of complex numbers, for example.
Therefore, it could be used with the original poster's
infinite-precision rational numbers. See

http://home.earthlink.net/~jrcarter010/pragmarc.htm

or the mirror at www.adapower.com

-- 
Jeff Carter
"You couldn't catch clap in a brothel, silly English K...niggets."
Monty Python & the Holy Grail

Re: Large numbers (or is Ada the choice for me?)

[Hans Georg Schaathun]

On Fri, 9 Mar 2001 18:28:43 -0500, Marin David Condic
  <marin.condic.auntie.spam@pacemicro.com> wrote:
: Well, let me check a few assumptions. 1) We can never run out of numbers.
: (Go ahead. Use all you want. We'll make more! :-) 2) We *can* and *will*
: eventually run out of memory. Hence, even if you did all the math with some
: sort of fractional representation rather than a decimal representation, it
: would be possible to construct numbers that exceed the capacity of the
: machine.

That is just as simple and likely as creating a problem it takes 50 years
to solve (with infinite memory resources).  The solution is rather simple,
the program returns error, `sorry, sam, your problem is to large'.

I am certainly aware that I won't be able to solve all the problems
I might want to create, but test runs in maple indicates that _this_
problem is solvable if memory is handled with care.

:           Hence, I think it stands to reason that you would be off on a
: fool's errand to insist on no approximations or limitations whatsoever.

I don't insist on no limitations.  I accept the limitations of memory 
and CPU resources, but I want to do as much as possible within these
limits.  My problem is primarily to determine whether the system has
integer solutions or not, which means that I can't accept (not even risk)
any rounding errors of � or more.  I doubt that floating point can save 
significant amounts of memory with this requirement.

: There has to be some sort of practical upper limit imposed by the available
: memory if nothing else.

Yes, so I won't cry over problems which can't be solved.

: As I said elsewhere, I rather hastily picked a bad example - but I think the
: point still stands that one will have to live with some sort of
: approximation on the representation - even if in practice, it may be so
: small as to not matter.

Wrong, my outset is to solve a couple of practical problems, not to 
solve any problem you might think of.

:-- Hans Georg
-- 
Signature en panne.

Modular type (Re: Large numbers)

[Hans Georg Schaathun]

On Fri, 09 Mar 2001 16:59:32 -0500, Tucker Taft
  <stt@averstar.com> wrote:
: My friends in "experimental mathematics" (sounds like fun, eh?) generally
: prefer to use arbitrary-precision packages based on the Chinese
: remainder theorem, because that allows large multiplications to
: be performed very efficiently.  Essentially a number is represented
: by its value modulo a series of prime numbers, typically those just
: less than 2**31.  Multiplication can then be done by 
: multiplying the individual "digits" independently.  A few dozen "digits"
: is usually enough to handle some very large numbers. 

Great hint;  I should have thought of this before.  Thank you.

But it raises two more questions.

1) Division.
If I remember correctly, that is NP-hard; though that does not really
matter since our numbers are bounded to 32 bits.  I was rather disappointed
to see that Ada does division completely wrong (it would be better not to
do it at all).  What is the best way to do division?  A linear search for
the inverse requires 2*10^9 multiplications, which is about as many as
required for all the rest of the problem.  Is this really the preferred
algorithm?

2) Dynamic modulus.
Is it in any way possible to choose the modulus for a modular type 
runtime, e.g. by parameter to the program?  Or must a dozen mod-types
be defined with hardcoded modulus?  (Barring of course, the possibility
to define modular types from scratch.)

:-- Hans Georg
-- 
Signature en panne.

Re: Modular type (Re: Large numbers)

[Florian Weimer]

georg@ii.uib.no (Hans Georg Schaathun) writes:

> If I remember correctly, that is NP-hard; though that does not really
> matter since our numbers are bounded to 32 bits.  I was rather disappointed
> to see that Ada does division completely wrong (it would be better not to
> do it at all).  What is the best way to do division?  A linear search for
> the inverse requires 2*10^9 multiplications, which is about as many as
> required for all the rest of the problem.  Is this really the preferred
> algorithm?

If you want to calculate the inverse of $x \in (\Z/n\Z)^\times$,
you  can use that $x^{\phi(n)}$ equals $1$, so you need only
$O(\log \phi (n))$ operations.  (To calculate $\phi(n)$, you need the
factorization of $n$, which is quite expensive, but needed only once).

IMHO, the Ada way of division is a bit strange, especially for prime
moduli.  OTOH, at least in the binary modulus case, dividing by zero
divisors (e.g. powers of two) is very common, so the Z/nZ approach
fails in this area.  This confusion could have been avoid only if
non-binary moduli were not in included in the language.

> 2) Dynamic modulus.
> Is it in any way possible to choose the modulus for a modular type 
> runtime, e.g. by parameter to the program?

No, there isn't.  The modulus has to be a static expression (which is
a stronger requirement then a compile-time constant).

Re: Modular type (Re: Large numbers)

[Hans Georg Schaathun]

On 15 Mar 2001 11:58:58 +0100, Florian Weimer
  <fw@deneb.enyo.de> wrote:
: If you want to calculate the inverse of $x \in (\Z/n\Z)^\times$,
: you  can use that $x^{\phi(n)}$ equals $1$, so you need only
: $O(\log \phi (n))$ operations.

Ooops, sure.  Sorry, I should have thought of that by myself.  Thx.

:                                (To calculate $\phi(n)$, you need the
: factorization of $n$, which is quite expensive, but needed only once).

Usually rather simple for prime numbers though, and I only want
prime moduli :-)

: > Is it in any way possible to choose the modulus for a modular type 
: > runtime, e.g. by parameter to the program?
: 
: No, there isn't.  The modulus has to be a static expression (which is
: a stronger requirement then a compile-time constant).

I wonder why this is necessary.  Is there an efficiency gain from using
built-in modular type compared to defining ones own modular type
with a run-time parameter as modulus?  (Assuming prime modulus.)

:-- Hans Georg
-- 
Signature en panne.

Re: Modular type (Re: Large numbers)

[Tucker Taft]

Hans Georg Schaathun wrote:
> 
> On 15 Mar 2001 11:58:58 +0100, Florian Weimer
>   <fw@deneb.enyo.de> wrote:
> : If you want to calculate the inverse of $x \in (\Z/n\Z)^\times$,
> : you  can use that $x^{\phi(n)}$ equals $1$, so you need only
> : $O(\log \phi (n))$ operations.
> 
> Ooops, sure.  Sorry, I should have thought of that by myself.  Thx.
> 
> :                                (To calculate $\phi(n)$, you need the
> : factorization of $n$, which is quite expensive, but needed only once).
> 
> Usually rather simple for prime numbers though, and I only want
> prime moduli :-)
> 
> : > Is it in any way possible to choose the modulus for a modular type
> : > runtime, e.g. by parameter to the program?
> :
> : No, there isn't.  The modulus has to be a static expression (which is
> : a stronger requirement then a compile-time constant).
> 
> I wonder why this is necessary.  Is there an efficiency gain from using
> built-in modular type compared to defining ones own modular type
> with a run-time parameter as modulus?  (Assuming prime modulus.)

If you want to deal with a dynamic modulus, you could use mod 2**32 types
and the explicit "mod" operator (for moduli < 2**16).  If your compiler
supports mod 2**64 types, then you could handle dynamic moduli up to
2**32, of course.

In retrospect, it does seem that the language could have allowed
a run-time modulus.  I suppose we were reluctant to define a new
kind of scalar type whose base range was not static.  The base range
is static for all others.

As far as division, it is clearly not the normal modular division,
but that is not particularly well defined for non-prime moduli,
so it wasn't really an option.

> :-- Hans Georg
> --
> Signature en panne.

-- 
-Tucker Taft   stt@avercom.net   http://www.averstar.com/~stt/
Chief Technology Officer, AverCom Corporation (A Titan Company) 
Burlington, MA  USA (AverCom was formerly the Commercial Division of AverStar:
http://www.averstar.com/services/ebusiness_applications.html)

Re: Large numbers (or is Ada the choice for me?)

[Robert I. Eachus]

Hans Georg Schaathun wrote:

> I need a tool to solve large systems of linear equations, with no
> floating point operations (or any other approximations) allowed.
> Even though I am not a seasoned programmer, I think I'll have to
> write the tool myself.
> 
> My question is, will it be reasonably simple to handle large
> rational numbers with Ada?  Is there any packages for this?

Others have answered this correctly, but let me suggest a better way to
approach your original problem.  If the linear equations you are dealing
with are inequalities, then you are trying to solve an (HP-hard) integer
programming problem.  If all of the equations are equalities, then there
is a much easier approach than using abusing a linear algebra package by
instantiating it with a rational type.

Firt find the solution using 64-bit float.  Then, since you stated that
you are only interested in integer solutions, convert the float answers
to integers, and check that all the equations are satisfied.  You may be
able to do this with Ada integer types, but it shouldn't strain the
resouces of the rational arithmetic packages that come with Ada
compilers.

The only remaining problem is that you have to be able to determine
whether or not you are rejecting an otherwise valid solution because the
rounding from float to integer was inaccurate.  If you compute the
determinant of the matrix M in aM = b, and compare it to 0.5/Epsilon you
should be okay.

If your system of equations is too large, or the constants are large,
you may have to resort to the rational arithmetic approach.  An
intermediate choice is to compute the inverse of M above using LUP
decomposition of M.  M' = P'U'L', so since  aM = b, a = bP'U'L'.  P, and
P inverse are permutations of the identity matrix, so they don't add any
error, and U' and L' should be much more accurate than M' itself.  In
fact, by choosing P correctly you should minimize the determinants of U
and L... 
  
> I guess I will manage to implement the rational numbers without
> too much hardship, but I really don't feel like implementing
> arithmetics on large integers.

If you know the size of the maximum intermediates in advance, you can
use the Chinese Remainder trick.  AS long as you choose a vector of
large primes, you can use the extended GCD algorithm to find inverses. 
But always verify that your answers do solve the original equations.  If
any of your intermediate values would be out of range, you will still
get an answer, but possibly an invalid one.

Re: Large numbers (or is Ada the choice for me?)

[Brian Rogoff]

On Mon, 19 Mar 2001, Robert I. Eachus wrote:
> Hans Georg Schaathun wrote:
> 
> > I need a tool to solve large systems of linear equations, with no
> > floating point operations (or any other approximations) allowed.
> > Even though I am not a seasoned programmer, I think I'll have to
> > write the tool myself.
> > 
> > My question is, will it be reasonably simple to handle large
> > rational numbers with Ada?  Is there any packages for this?
> 
> Others have answered this correctly, but let me suggest a better way to
> approach your original problem.  If the linear equations you are dealing
> with are inequalities, 

That is not possible. It is possible for a system of linear inequalities
to be a system of linear equations though ;-).

> then you are trying to solve an (HP-hard) integer
> programming problem.

If you're trying to solve an integer programming problem, there's only a
few cases where solving an LP problem makes sense. 

> If all of the equations are equalities, then there

All equations are equalities by definition. 

OK, sorry Robert, I'm in a pesky mood :-}

-- Brian