Re: Euler's totient function

[Jordi Gutiérrez Hermoso]

On 16 November 2010 09:21, Fotios Kasolis <address@hidden> wrote:
> Does Octave have Euler’s totient function? If not, what do you think about
> including it?

I think this kind of math is beyond Octave's scope. Pari and Sage
already do this kind of computations well. If Matlab has this
function, I suppose it's a good idea to include it in

> function x = phi (n)
> x = sum (gcd ([1:n], repmat (n, 1, n)) == 1)
> endfunction

This is a pretty bad algorithm. It's worse than factoring n, because
you need to do more divisions in the Euclidean algorithm than the
number of trial divisions you would need in order to factor n.

I tried reading Pari's source to see what they do, but it's hard for
me to decipher its code, because I'm unfamiliar with it. They seem to
be generating successive primes and testing up to those instead, and
if you find a number with nontrivial gcd, then you can also discard
all of its multiples less than p.

Point is, there are better algorithms, and perhaps they should be left
to programs specialised for it.

- Jordi G. H.