This shows you the differences between two versions of the page.
Next revision | Previous revision | ||
en:group:seminars:20050602 [2009/04/07 11:17] 127.0.0.1 external edit |
en:group:seminars:20050602 [2016/06/23 11:26] (current) |
||
---|---|---|---|
Line 3: | Line 3: | ||
date_dt : 2005-06-02 | date_dt : 2005-06-02 | ||
title : A new result in the average case analysis of the binary GCD algorithm | title : A new result in the average case analysis of the binary GCD algorithm | ||
- | speaker : Gérard Maze | + | speaker : GĂ©rard Maze |
affiliation : | affiliation : | ||
time : | time : | ||
Line 15: | Line 15: | ||
==== abstract ==== | ==== abstract ==== | ||
The binary Euclidean Algorithm is a variant of the classical | The binary Euclidean Algorithm is a variant of the classical | ||
+ | Euclidean algorithm. It avoids divisions and multiplications, except | ||
+ | by powers of two, so is potentially faster than the classical | ||
+ | algorithm on a binary machine. In this talk, we will define the | ||
+ | binary Euclidean algorithm and outline its history from 1976 to | ||
+ | nowadays. We will present Richard Brent's heuristic model and sketch | ||
+ | the proof of the existence of a unique limiting distribution that | ||
+ | plays a central role in this model. | ||