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. | ||