Original scientific paper

Ties in Worst-Case Analysis of the Euclidean Algorithm

Brian Hopkins ; Saint Peter’s University, Jersey City, NJ 07 306 USA
Aram Tangboonduangjit ; Mahidol University International College, 999 Phutthamonthon Sai 4 Rd, Salaya, Phutthamonthon District, Nakhon Pathom 73 170, Thailand

Abstract

We determine all pairs of positive integers below a given bound that require the most division steps in the Euclidean algorithm. Also, we find asymptotic probabilities for a unique maximal pair or an even number of them. Our primary tools are continuant polynomials and the Zeckendorf representation using Fibonacci numbers.

Keywords

Euclidean algorithm; continuant polynomials; Fibonacci numbers

Hrčak ID:

252595

URI

https://hrcak.srce.hr/252595

Publication date:

10.3.2021.

Visits: 653 *