Talk:Arbitrary-precision arithmetic

From Wikipedia, the free encyclopedia

Didn't you want to talk about big floating-point numbers ? Are some people interessed ?

---

I moved the following HTML comments from the article source over to this talk page. They may be more useful here:

<!-- Please give known applications to specific problems, rather than making vague statements that bignum arithmetic is used in [[theoretical physics]] etc. -->

<!-- TODO: mention division algorithms, and hence square root etcetera. Mention arithmetic-geometric mean algorithms for computing e^x, trig functions, pi, etcetera. -->

—Herbee 20:57, 23 April 2006 (UTC)

[edit] The newly-added Infinite Precision section.

Shouldn't this be arbitrary precision as well? I'm not familiar with the work being referenced, but I'm fairly certain that there is no such animal. Trying to get infinite precision off of 4/3 * pi just isn't happening on computers with finite memory any time soon. SnowFire 16:16, 22 May 2006 (UTC)

I agree. It's the usual confusion between "arbitrarily large" and "infinite". —Steven G. Johnson 16:45, 22 May 2006 (UTC)

The text basically describes symbolic algebra. Fredrik Johansson 16:52, 22 May 2006 (UTC)

You're right, upon closer reading symbolic algebra seems to be what was intended by the text. It's still misleading to call it "infinite precision", however, since (a) the symbolic expressions have arbitrary (limited by memory) but finite size, which directly corresponds to a form of finite precision, and (b) you're not really doing "arithmetic" until you calculate the numeric result, and that is done with arbitrary but finite precision. Besides, if you Google for "infinite precision arithmetic", it seems that this term is mainly used as a synonym for arbitrary precision. —Steven G. Johnson 16:59, 22 May 2006 (UTC)

I agree with all of the above given suitable context, but not with the text in the article which reads "...infinite-precision arithmetic, which is something of a misnomer: the number of digits of precision always remains finite...". I would argue that any representation for which there is a bijective mapping onto the set being modelled is precise. It's not infinite precision that's the problem, it's trying to represent elements of an infinite set on a finite state machine. IMHO, it is not an error to describe bignum arithmetic as "infinite precision" if it is operating over a finite set, an obvious example being the integers modulo N, for not-extremely-large N. --Will

Sure, and a one-bit integer is "infinite precision" in your sense, as long as you are only trying to represent the set {0,1}. As far as I can tell, however, that's simply not the way the term "precision" and especially "infinite precision" is used in the setting of numeric computation. In this context, the "precision" of a number is the number of significant digits that are specified (or some equivalent measure of information content). (Yes, the general English meaning is more vague than that...most English words are, but that doesn't prevent them from having a more, ahem, precise meaning in a technical context.) I think the meaning that you are describing would be better termed "perfect precision". —Steven G. Johnson 04:03, 28 May 2006 (UTC)

If a number is represented in a format which provides n base-d digits of precision (even this makes unnecessary assumptions about representation), then the error is proportional to d^-n. Thus n = -log(error), with n going to infinity as error goes to zero. I would have said that if the error is exactly zero for all operations and for all operands, then the precision is infinite. This is applicable to the modular arithmetic case (including the n=1 case you mentioned), but not for general symbolic algebra systems, where the size of the expression tree is artificially bounded by the machine's available state; I therefore don't agree with the section which keeps appearing. I'm not saying that "infinite precision" is a more appropriate term than "arbitrary precision" for finite number systems, merely that it's not inaccurate. But on reflection perhaps I was misinterpreting the sentence; which on re-reading is perhaps only dismissing it as a misnomer when used as a synonym for arbitrary precision. --Will (86.141.151.165 11:06, 28 May 2006 (UTC))

Be careful not to confuse accuracy/error with precision. 3.000000000000000 is very precise, but it is not a very accurate representation of, say, π. —Steven G. Johnson 18:54, 28 May 2006 (UTC)

You are wrong. 4/3*pi is a computable number, thus it can be represented in finite manner in the memory of the computer. There is an example in the references section. Sounds like you don't know what you're talking about.  Grue  06:17, 28 May 2006 (UTC)

It's the same thing that happens if I type 4/3*Pi in Mathematica. Symbolic algebra: expressions evaluate to expressions, with pointers to code to compute the atomic elements numerically with any desired precision. The only difference between Mathematica and the Lisp library is that the latter shows a numerical value instead of the underlying expression in the REPL. Fredrik Johansson 09:43, 28 May 2006 (UTC)

The set of computable reals is infinitely large. The set of states for a machine running mathematica (or any similar package) is finite. Therefore there exist pairs of distinct computable numbers which have identical representation within the machine. Where this happens, there is nonzero error. You can't have infinite precision if there's error. --Will (86.141.151.165 11:16, 28 May 2006 (UTC))

No, some computable numbers are just too complicated to fit in memory and they can't be represented. So, only finite set of different computable numbers fits in any given computer. As for symbolic computation, I think there are some noticeable differences. In case of π, there is a symbol for a number, but many computable numbers don't have any symbol nor can be represented as a finite composition of arithmetic operations on numbers that have a symbol (there are also numbers that have a symbol, but are not computable, like Chaitin's constant).  Grue  12:44, 28 May 2006 (UTC)

Grue, this article is about arithmetic and that means computation of a numeric result. By definition, every computable number can be represented by a finite-length (though possibly very large) computer program that computes it to any arbitrary (but not infinite) precision in finite time. The representation of a number by a computer program is perfectly precise in the sense of determining a given real number uniquely, but does not provide infinite-precision arithmetic. —Steven G. Johnson 19:15, 28 May 2006 (UTC)