CFRAC

The continued fraction factorization method (CFRAC) is an integer factorization algorithm. It is a general-purpose algorithm, meaning that it is suitable for factoring any integer n, not depending on special form or properties. It was described by D. H. Lehmer and R. E. Powers in 1931, and developed as a computer algorithm by Michael A. Morrison and John Brillhart in 1975. Implementation used was the same published with allocator Hoard.

Inputs and trace's reports

We collect 5 traces of CFRAC's allocation when invocated with these inputs (in order of complexity):
  1. 23533 => report input 1
  2. 1000000001930000000057 => report input 2
  3. 327905606740421458831903 => report input 3
  4. 4175764634412486014593803028771 => report input 4
  5. 41757646344123832613190542166099121 => report input 5
You can find all MallocLab's traces for CFRAC here.

Allocator's configurations

  1. BSA => Original BSA with page allocation and alternate split side (AS)
  2. TLSF => Two Level Segregate allocator
  3. BSA-- => BSA with no split or coalesce and no AS
  4. BSA++ 10 => BSA++ with no AS, popularity index threshold 10
  5. BSA++ (npa) 10 => BSA++ with no AS, no page allocatione (npa), popularity index threshold 10
  6. BSA++ AS 10 => BSA++ with AS, popularity index threshold 10
  7. BSA++ AVG 10 => BSA++ with no AS, average popularity threshold 10
  8. BSA++ AVG (npa) 10 => BSA++ with no AS, npa, average popularity threshold 10
  9. BSA++ AS AVG 10 => BSA++ with AS, npa, average popularity threshold 10
  10. BSA++ VAR 345 => BSA++ with no AS, popularity index threshold >= 15, variance popularity threshold 345
  11. BSA++ VAR (npa) 805 => BSA++ with no AS, npa, popularity index threshold >= 15, variance popularity threshold 805
  12. BSA++ VAR AS 920 => BSA++ with AS, popularity index threshold >= 15, variance popularity threshold 920
Some of these allocators have been tested with different threshold: In this page we show only the winner for each type of allocator's configuration. Read BSA or BSA++ description in order to understand all features listed above.

Time

Space

Return to the main page