OpenEuphoria

1. math:gcd is incorrect

• Posted by bill May 07, 2012
• 1901 views

The manual:

62.7.7 GCD
include std/math.e
namespace math

public function gcd (atom p, atom q)

Returns the greater common divisor of to atoms

Parameters:
p : one of the atoms to consider
q : the other atom.

Returns:
A positive atom, without a fractional part, evenly dividing both
parameters, and is the greatest value with those properties.

Comments:
Signs are ignored. Atoms are rounded down to integers.
Any zero parameter causes 0 to be returned.
....

Evidence:

	include std/math.e 
	? gcd(0, 48) 
 
	returns 0 

This is simply wrong.

GCD (0, 48) = 48

1. By definition a greatest common divisor could not be 0.
Division by 0 is undefined (and 1/0 != INF).

2. 0 is divisible by 48.

Pseudocode GCD (from Knuth pp.319-20)
quoted in Wikipedia article on GCD algorithm

	function gcd(a, b) 
	   while b != 0 
	      t := b 
	      b := a mod b 
	      a := t 
	   return a 

Note: formally gcd(0, 0) is undefined and should be an
error just as much as division by zero is an error.

Theorem 2.1 Given any two integers a and b, not both zero,
there is a unique integer d, called their greatest common
divisor, with these properties: 1: d | a and d | b;
2: if d1 | a and d1 | b then d1 | d;
3: d > 0.

WJ Leveque Fundamentals of Number Theory p.31

3. Re: math:gcd is incorrect

• Posted by jimcbrown (admin) May 07, 2012
• 1788 views

Agreed. GCD(0, 48) is the same as GCD(48, 0) which is 48.

I'll take a stab at fixing this.

Agreed. The limit of 1/x becomes arbiturarily large as x approaches 0, but that's different from stating that 1/0 is equal to infinity.

Except in trivial rings and wheel groups...

Technically, this is correct. Sometimes GCD(0, 0) is explicitly considered being equal to zero for similiar reasons that 0^0 is considered equal to 1.

5. Re: math:gcd is incorrect

• Posted by jimcbrown (admin) May 07, 2012
• 1733 views

They are in the sense that in both cases the functions are redefined by mathematicians such that they return a value.

Well, division is the inverse of multiplication. It's true that it's common to define division (at least in basic arthimetic) excluding zero as a divisor, this leads arthimetic to be incomplete.

Alternatively, you could allow division by zero, but then you'd have contradictions. This seems like a deal-breaker, and it is most of the time, but probability works pretty well in spite of it. For example, the probability of hitting a smaller area within a larger one (e.g. hitting the 1-square inch bulls eye of a much larger dart board) is the area of the smaller divided by the area of the larger. However, the probability of hitting a single point overall in the larger area is zero, so if you attempt to compute the probability of hitting the larger area (out of the entire larger area, so larger area / larger area or P(1) )by summing up the probability of hitting any individual point, this infinite summation will lead you to a probability of 0% instead of 100%!

Back to division by zero. 1 / 0 = some imaginary number z, but then 0 * z would equal 0 and not 1, leading to a contradiction.

Even worse, 0 / 0 could equal any number. After all, 0 * z = 0, so 0 / 0 = z, but 0 * 1 = 0, so 0 / 0 = 1, and 0 * 0 = 0, so 0 / 0 = 0, 0 * i = 0, so 0 / 0 = i, etc. This makes 0 / 0 indeterminate.

1. 0^0 is def = 1 because lim x->0 x^x = 1 and x^x is continuous  
   on all real x != 0 

So? x to the power of x is not continuous when x equals 0, and the limit of a value is different from the value.

Additionally, the limit of 0 to the power of x as x approaches 0 is 0. This gives a different answer than your formula, which means the value of 0 to the power of 0 is indeterminate.

0 to the power of 0 is itself indeterminate. One way to define power of zero is like this:

x^0 = x^-1 * x^1 

Of course, by definition

x^-1 = 1/(x^1) 

This gives

x^1 / x^1 = x/x 

When x is not equal to zero, it's obvious that this is equal to one. But when x is equal to zero, then this ends up as 0/0 which is indeterminate as discussed above.

Following this definition, 0 to the power of 0 can be argued to be anything (e.g. 0, 1, i, -264, etc...), the same way 0/0 is.

The real reason that 0 to the power of 0 is considered as equal to 1 is because it is useful to do so as it simplifies things like the binomial theorem by removing special cases.

Likewise, and to quote Wikipedia,

By normalization, are you refering to normalized vectors, normalization property, or statistical normalization? None of these seem to fit.

Perhaps you mean something like "to make the function seem normal, as applies to common sense, by replacing its undefined and indeterminate cases with values that seem to make sense, according to common sense".

In that case, I'm fine with your definition, but I'd argue:

Normalization: POW(0,0) = 1: POW(x,x) = x^x 

7. Re: math:gcd is incorrect

• Posted by Selgor May 09, 2012
• 1645 views

Just interested. Where did the above info come from ?.

Selgor

9. Re: math:gcd is incorrect

• Posted by EUWX May 09, 2012
• 1645 views

At the level of writing a division algorithm for a computer language, it is the slowest compared to add, subtract, or multiply.
It is therefore handled thusly:

If Left_Arg = Right_Arg, then return 1 and exit.
If Right_Arg = 0, then return sign of Left_Arg on infinity symbol and exit.

Proceed normally with division.

11. Re: math:gcd is incorrect

• Posted by bill May 10, 2012
• 1572 views

EUWX is saying

'Because I prefer ...'

Because I prefer 0/0 = 1

I prefer it when: 
 
 0 * 2     0      
 _____  =  _  =  1 * 2 = 2 
 
   0       0              
    
and  0 * 2  = 0 
              _  = 1   
 
	      0  

Should any person take notice of him?

13. Re: math:gcd is incorrect

• Posted by bill May 10, 2012
• 1553 views

I apologise for being so sharp.

I wasn't being personal.

What I was trying to point out is not that Eu is
superior to APL. I don't believe that. I do
believe that Eu4 has faults. Eu is weakly typed.

I am interested in Eu as a scripting language not
for serious programming.

"APL has been" was unnecessarily dismissive.

What I said:

1 Using 0/0 = 1 can lead to major inconsistencies
- such as 1 = 2 - depending on evaluation order.

From what I have seen APL gets away with 0/0 = 1
because it uses a fixed eveluation order
(right to left) unless brackets intervene. Also
it does not respect precedence for operators.

You said:

I like the following understanding.
x divided by 0 ...... (plus or minus) infinity if x is not 0
0 divided by 0 ...... is 1 because anything divided by itself
results in 1.

You gave no indication of understanding the consequences of such definitions.

We have numbers/symbols +inf -inf
Division by zero is an error/inf unless it is zero / zero
when it is fine. Reduction of equation have to be done in a fixed order.

Question: If anything / anything = 1 then does inf / inf = 1?

That, I considered trolling.

You followed up with a reference to an APL paper and a
comment on machine division. And the killingly funny
source for 0/0 = 1 ancient middle eastern philosophy.

The original discussion was about GCD and particularly that
GCD(0,4) is 4 not 0 as in the Euphoria Maths library.
GCD(0,0) is undefined because there is no uniquely defined
common divisor.

GCD(0,0) is defined as 1 or 0
- 0 because it is common,
- 1 because it is a divisor.

Knuth gives GCD code which would give GCD(0,0) = 0.
Lattice theory would require GCD(0,0) = 1, LCM(0,0) = 0
Neither is convincing.

Defining GCD(0,0) = 1 is useful in that 1 is a divisor.
My initial thought was to disqualify GCD(0,0) but
rethinking I would go with 1. (pace Knuth)

Again, I apologise for being offensive.