OSDev.org

Posted: **Tue May 22, 2007 4:16 am**

AJ wrote:
Code: Select all
a = b
...
(a-b)(a+b) = b(a-b)
a+b = b

a-b = 0 therefore you're dividing by 0.

I'm particularly fond of the following:

a = 0.9999...
10a = 9.99999...
10 - a = 9
9a = 9
a = 1

1 + 1 = 3, for sufficiently large values of 1

Posted: **Tue May 22, 2007 10:26 am**

Brendan wrote:The most common problem is that CPUs work in binary and some decimal numbers can't be represented precisely in binary. For example, "0.1" in binary repeats forever (it becomes 0.0001100110011001100110011...), so the CPU will either truncate it or round it to make it fit. This means that "(1 / 10) * 10" might give the answer 1.00000000000001 because the intermediate value "1 / 10" can't be represented precisely.

WRT the binary representation of any fraction, is it true (proof request) that all elements in Q are representable in a finite amount of bits , possibly with a repetition of the last N bits infinitely many times?

If so, you could make the arbitrary precision integer class also represent an arbitrary precision rational, without resorting to an explicit type of division encoded into a type.

Posted: **Tue May 22, 2007 12:35 pm**

Err yes, as two numbers :p.

Posted: **Tue May 22, 2007 1:19 pm**

Zekrazey1 wrote:Err yes, as two numbers :p.

That was, without an implicit division.

Posted: **Tue May 22, 2007 3:49 pm**

Candy wrote:
Brendan wrote:The most common problem is that CPUs work in binary and some decimal numbers can't be represented precisely in binary. For example, "0.1" in binary repeats forever (it becomes 0.0001100110011001100110011...), so the CPU will either truncate it or round it to make it fit. This means that "(1 / 10) * 10" might give the answer 1.00000000000001 because the intermediate value "1 / 10" can't be represented precisely.
WRT the binary representation of any fraction, is it true (proof request) that all elements in Q are representable in a finite amount of bits , possibly with a repetition of the last N bits infinitely many times?

If so, you could make the arbitrary precision integer class also represent an arbitrary precision rational, without resorting to an explicit type of division encoded into a type.

The only problem is that the set Q is infinitely large, and that with any finite amount of bits you could not represent all elements in Q.

Apart from that, you could create a floating point number with an repetition field encoded:
{sign, exponent, mantissa, repetition}
this field determines the amount of bits from the end of the mantissa that should be repeated. You could define that a value of 0 means that an infinite series of 0s follow the sequence given (i.e, the number is exact)
This notation can store all rationals with finite nominators/denominators provided that the encoding contains sufficient bits.

Proof of concept:
given the standard tail division, we have a nominator, denominator and a result. we start with subtracting the nominator with the denominator * a power of two, which will give us the exponent, one bit in the mantissa, and a new value strictly smaller than the nominator. We then proceed by shifting the denominator used one bit to the right, and attempt another subtraction, which results in another bit for the mantissa and so on. We can continue this process until the denominator has obtained its original value. The net result is that we have the result + remainder of integer division.
We can continue this process by shifting the remainder one bit and attempting to subtract the denominator, which gives us another bit. When iterating for many steps, the remainder can either become zero, which is stable, or repeat a certain loop.
The interesting part is that it that the remainder < denominator, and that after (denominator) iterations either the remainder must have become 0, or that there is one value for the remainder that has reappeared. In the first case, the number can be represented in any standard float of enough precision, as further iteration will always generate 0s, in the other case, there is a number of iterations after which the remainder attains a previous value. Since there is no other state involved, after the same amount of iterations the same remainder will reappear, and the same bits will be produced. This results in an infinite repetition of the same sequence of an finite size, which can be encoded using the repetition field above. We also know that the length of the repetition is at most (denominator) bits. (Excercise for the reader to proof that it is at most half that number.)

Using a similar method, one can do further division of rationals (as the result is a rational too), as well as other basic math operations.

Posted: **Tue May 22, 2007 4:03 pm**

jnc100 wrote:This argument has probably been posted before but I can't be bothered to go back through the post to check:

If two numbers are different then there has to be a number between them.

Can anyone suggest a number between 0.999999.... and 1?

Thought not.

YES!

anon19287473 wrote:So i propose an imaginary number to represent 1-0.99999999999....., it will be a 'w' with a big swoosh at the end! ...

It's a 'w' with a big swoosh at the end, I've already discussed this.

Thought not.

Guess I proved you wrong!

Posted: **Tue May 22, 2007 4:27 pm**

Hi,

Candy wrote:
Brendan wrote:The most common problem is that CPUs work in binary and some decimal numbers can't be represented precisely in binary. For example, "0.1" in binary repeats forever (it becomes 0.0001100110011001100110011...), so the CPU will either truncate it or round it to make it fit. This means that "(1 / 10) * 10" might give the answer 1.00000000000001 because the intermediate value "1 / 10" can't be represented precisely.
WRT the binary representation of any fraction, is it true (proof request) that all elements in Q are representable in a finite amount of bits , possibly with a repetition of the last N bits infinitely many times?

That depends - can you define "all elements of Q"? I think Q was the inventor in James Bond movies, and I assume he only had a single integer (possibly in octal) like 007 did...

Candy wrote:If so, you could make the arbitrary precision integer class also represent an arbitrary precision rational, without resorting to an explicit type of division encoded into a type.

You could have a significand, an (optional?) exponent, a "recurring" and a "recurring length", where a number like "0.10" would be represented as significand = 0, exponent = -1, "recurring" = 0011b and "recurring length" = 4. In this case you'd be able to represent any rational number that fits in the significand and "recurring", and would lose precision for things that don't fit.

The problem is writing the code to do it. For example, if "recurring" is 32 bits wide then for division you'd need a 32 entry stack of remainders to detect the number of recurring bits, and I've got no idea how you'd go about adding, multiplying or dividing 2 numbers with recurring digits of different lengths.

Alternatively, storing a significand, divisor and exponent is theoretically easier, as the algorithms to do it are well documented (e.g. normal binary math algorithms, and the Stein algorithm cover most of it). Something tells me that the width of the divisor determines how many recurring digits it supports, but I need to do more thinking before I call that idea more than a guess.

To be honest I've been experimenting with arbitrary precision "S/D * 2^E" numbers - unfortunately it's surprisingly complex to do efficiently without unnecessary precision loss.

For an example, for a simple operation like adding 2 numbers you end up finding the lowest common multiples (which involves finding greatest common divisors) and then doing 2 multiplications and 2 divisions just to get the divisors the same. After that you'd shift significands and increase/decrease exponents to get the exponents the same. Then you'd add the significands. Lastly you'd work out another greatest common divisor and divide the resulting significand and divisor by the GDC.

The entire process looks like this:

Code: Select all

5/8 * 2^2 + 7/12 * 2^1
= 5*LCM/8 / LCM * 2^2 + 7*LCM/12 / LCM * 2^1       ;Make divisors the same
= 5*24/8 / 24 * 2^2 + 7*24/12 / 24 * 2^1
= 5*3 / 24 * 2^2 + 7*2 / 24 * 2^1
= 15 / 24 * 2^2 + 14 / 24 * 2^1
= 30 / 24 * 2^1 + 14 / 24 * 2^1              ;Make exponents the same
= (30 + 14) / 24 * 2^1
= 44 / 24 * 2 ^ 1
= 44/GCD / 24/GCD * 2^1                 ;Simplify
= (44/4) / (24/4) * 2^1
= 11/6 * 2^1

Ironically, multiplication is probably faster than addition, as it requires less multiplication and division of bits. It's easy to find the inverse of a number though (just swap the significand and divisor), which makes division easy to implement once multiplication works.

I'm thinking AND, OR and XOR are worse than addition. I'm also wondering if a NOT operation could be done by negation (change the "significand is negative" flag, and test the negative flag during AND, OR and XOR operations). For e.g. for "negative number AND negative number", you'd set result's negative flag and do an NAND operation for each bit in the significand.

Cheers,

Brendan

Posted: **Tue May 22, 2007 5:12 pm**

As im new to this forum i feel it is my duty to throw in a few funny pointers.

First of all, in my oppinion, both
.9999999999...
and
.9999999999... + infinity^-1
equals one allthough i understand the argument that .9999999999... is not a real number and it is only if you want to represent in another way than writing .9999999999....

Now to the fun part.

this is widely know, and allso the result is:
1/2 + 1/4 + 1/8 + 1/16... = ?
(you see of course that it can easily be represented in binary)

And one with primes:
(1 - 1/2)(1 - 1/3)(1 - 1/5)(1 - 1/7)... = ?

As im a big fan of primes i especially like the last one.

Regards

Posted: **Wed May 23, 2007 1:14 am**

Candy wrote:
Zekrazey1 wrote:Err yes, as two numbers :p.
That was, without an implicit division.

What's wrong with an implicit division? It's no worse than the implicit multiplications and additions in the binary representations of integers.

The only problem is that the set Q is infinitely large, and that with any finite amount of bits you could not represent all elements in Q.

I read the question as 'given any q in Q, can that q be represented in a finite number of bits' (which you later addressed anyway).

Posted: **Wed May 23, 2007 1:48 am**

anon19287473 wrote:
jnc100 wrote:This argument has probably been posted before but I can't be bothered to go back through the post to check:

If two numbers are different then there has to be a number between them.

Can anyone suggest a number between 0.999999.... and 1?

Thought not.
YES!

anon19287473 wrote:So i propose an imaginary number to represent 1-0.99999999999....., it will be a 'w' with a big swoosh at the end! ...
It's a 'w' with a big swoosh at the end, I've already discussed this.

Thought not.
Guess I proved you wrong!

You havn't proven anything. You need to prove that your 'w with a big swoosh' is in the set of real numbers and that it's not equal to 0. In other words, all you've done is changed the argument about the equality of 0.99~ and 1 to an argument about the existence of a real non-zero swooshy w.

Posted: **Wed May 23, 2007 7:17 am**

anon19287473 wrote:
anon19287473 wrote:So i propose an imaginary number to represent 1-0.99999999999....., it will be a 'w' with a big swoosh at the end! ...
It's a 'w' with a big swoosh at the end, I've already discussed this.

Thought not.
Guess I proved you wrong!

Oh yeah, I forgot about the swoosh. How silly of me...

Posted: **Thu May 24, 2007 9:53 am**

Brendan wrote:Hi,

Candy wrote:
Brendan wrote:The most common problem is that CPUs work in binary and some decimal numbers can't be represented precisely in binary. For example, "0.1" in binary repeats forever (it becomes 0.0001100110011001100110011...), so the CPU will either truncate it or round it to make it fit. This means that "(1 / 10) * 10" might give the answer 1.00000000000001 because the intermediate value "1 / 10" can't be represented precisely.
WRT the binary representation of any fraction, is it true (proof request) that all elements in Q are representable in a finite amount of bits , possibly with a repetition of the last N bits infinitely many times?
That depends - can you define "all elements of Q"? I think Q was the inventor in James Bond movies, and I assume he only had a single integer (possibly in octal) like 007 did...

Z := 0 : {x <- Z | x+1, x-1}
Q := { x,y <- Z, y != 0 | x/y }

Posted: **Thu May 24, 2007 1:10 pm**

Zekrazey1 wrote:
anon19287473 wrote:
jnc100 wrote:This argument has probably been posted before but I can't be bothered to go back through the post to check:

If two numbers are different then there has to be a number between them.

Can anyone suggest a number between 0.999999.... and 1?

Thought not.
YES!

anon19287473 wrote:So i propose an imaginary number to represent 1-0.99999999999....., it will be a 'w' with a big swoosh at the end! ...
It's a 'w' with a big swoosh at the end, I've already discussed this.

Thought not.
Guess I proved you wrong!
You havn't proven anything. You need to prove that your 'w with a big swoosh' is in the set of real numbers and that it's not equal to 0. In other words, all you've done is changed the argument about the equality of 0.99~ and 1 to an argument about the existence of a real non-zero swooshy w.

It's an imaginary number... NOT a real number. *snicker*

Posted: **Thu May 24, 2007 2:57 pm**

Copycat

.

*grabs snicker and munches it*

Posted: **Fri May 25, 2007 3:09 pm**

Speaking as a mathematician, you can take it from me that 0.999999 recurring does equal one. The differential and integral calculus, for a start, would come crashing down around our ears if it didn't.

And it is certainly not an imaginary number.

OSDev.org

0.99999... != 1