Analysis of the Binary Euclidean Algorithm

reportActive / Technical Report | Accession Number: ADA029130 | Open PDF

Abstract:

In this paper the author analyzes a continuous model of the binary algorithm and finds the expected number of iterations. The results agree with the observed behavior of the algorithm much better than those predicted by Knuths lattice-point model.

Author(s):
Brent, Richard P.
Author Organization(s):
CARNEGIE-MELLON UNIV PITTSBURGH PA DEPT OF COMPUTER SCIENCE
Descriptive Note:
Interim rept.
Supplementary Note:
Prepared in cooperation with Australian National Univ., Canberra. DOI: 10.21236/ADA029130
Pagination:
0039

Security Markings

DOCUMENT & CONTEXTUAL SUMMARY

Distribution:
Approved For Public Release
Distribution Statement:
Approved For Public Release; Distribution Is Unlimited.

RECORD

Collection: TR
Identifying Numbers
Contract/Grant Number(s):
N00014-76-C-0370, NSF-MCS75-222-55
Project Number(s):
NR-044-422
Monitor Series:
ONR
 Subject Terms
Joint Capability Areas:
JCA_5_Command and Control; JCA_5.3_Planning; JCA_1.2_Force Preparation; JCA_1_Force Support; JCA_1.2.3_Educating; JCA_6_Net Centric
Communities of Interest:
Energy and Power Technologies
Descriptor(s):
*ALGORITHMS, *BINARY ARITHMETIC, DISTRIBUTION FUNCTIONS, ITERATIONS, THEOREMS
Field(s)/Group(s):
Statistics and Probability
Report Date:
1976 Jun 01