Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl: the Markov chain saw
 
PerlMonks  

Re^4: Algorithm for cancelling common factors between two lists of multiplicands

by QM (Parson)
on Aug 10, 2005 at 18:36 UTC ( #482708=note: print w/replies, xml ) Need Help??


in reply to Re^3: Algorithm for cancelling common factors between two lists of multiplicands
in thread Algorithm for cancelling common factors between two lists of multiplicands

Looking at my copy of The Art of Computer Programming: Seminumerical Methods, 3E, Knuth gives the worst case as:
O(GCD) ~= 4.785*log(N) + 0.6723
where N is the smaller argument to Euclid's algorithm. The average is much better:
Avg(GCD) ~= 0.1775*N
Update: hv pointed out that the approximation for the mean didn't look right. I went back to the source, and see that I pulled out an intermediate result (I have to read more closely in the future). So it's not the mean.

The mean is given as

Avg(GCD) ~= 1.9405*log10(N)
where N is the smaller argument to Euclid's algorithm, and ignoring a subtracted correction term based on the divisors of N.

-QM
--
Quantum Mechanics: The dreams stuff is made of

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://482708]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others making s'mores by the fire in the courtyard of the Monastery: (7)
As of 2019-10-14 23:43 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    Notices?