home *** CD-ROM | disk | FTP | other *** search
/ DP Tool Club 15 / CD_ASCQ_15_070894.iso / news / 4569 / goodies8 / math / sqpq.doc < prev    next >
Text File  |  1993-02-18  |  1KB  |  43 lines
  1. SQPQ - Square Root's Partial Quotients, by Joe Horn, 12/28/92.
  2. A Number Theory tool.
  3.  
  4. Turning square roots of integers into continued fractions via the
  5. usual FP INV method rapidly introduces round-off errors, and does not
  6. help in determining where the continued fraction begins to repeat.
  7.  
  8. The following program, SQPQ, uses a method which neatly avoids all
  9. round-off errors and automatically detects where the repetition
  10. begins.
  11.  
  12. INSTRUCTIONS: SQPQ takes the integer (not its square root!) as its
  13. input, and returns a list of the partial quotients of the continued
  14. fraction equal to the square root of the input.  The list terminates
  15. immediately after the last term of the repeating sequence.  Therefore
  16. the entire list, except for the first element, repeats.
  17.  
  18. EXAMPLE: What is the continued fraction for the square root of 18?
  19. 18  SQPQ  -->  { 4 4 8 }  which means
  20. SQRT(18) = 4+1/(4+1/(8+1/(4+1/(8+...  with 4 8 repeating.
  21.  
  22. EXAMPLE: 28  SQPQ  -->  { 5 3 2 3 10 }  which means
  23. SQRT(28) = 5+1/(3+1/(2+1/(3+1/(10+1/(3+1/(2+1/(3+1/(10+...
  24. with 3 2 3 10 repeating.
  25.  
  26. EXAMPLE: 16  SQPQ  -->  { 4 }  which means it's exactly 4.
  27.  
  28. %%HP: T(3)A(D)F(.);
  29. @ SQPQ, Square Root's Partial Quotients, by Joe Horn, 12/28/92
  30. \<< DUP \v/
  31.   IF DUP FP
  32.   THEN 0 1 1 \-> N S A B L
  33.     \<<
  34.       DO S A + B / IP DUP B * A - 'A' STO
  35.         N A SQ - B / 'B' STO
  36.         'L' 1 STO+
  37.       UNTIL B 1 ==
  38.       END A DUP + L \->LIST
  39.     \>>
  40.   ELSE SWAP DROP 1 \->LIST
  41.   END
  42. \>>
  43.