; fenderbecker's square reckoner (define bitwise-and logand) (define (isqrt n) (if (not (and (positive? n) (integer? n))) (error 'isqrt "must be positive integer") (let loop ((x n)) (let ((y (quotient (+ x (quotient n x)) 2))) (if (< y x) (loop y) x))))) (define (square? n) (let ((m (modulo n 128))) (if (positive? (bitwise-and (* m #x8bc40d7d) (* m #xa1e2f5d1) #x14020a)) #f (let ((large-mod (modulo n 3989930175))) ; (* 63 25 11 17 19 23 31) (and (let ((m (modulo large-mod 63))) (zero? (bitwise-and (* m #x3d491df7) (* m #xc824a9f9) #x10f14008))) (let ((m (modulo large-mod 25))) (zero? (bitwise-and (* m #x1929fc1b) (* m #x4c9ea3b2) #x51001005))) (let ((m (* #xd10d829a (modulo large-mod 31)))) (zero? (bitwise-and m (+ m #x672a5354) #x21025115))) (let ((m (modulo large-mod 23))) (zero? (bitwise-and (* m #x7bd28629) (* m #xe7180889) #xf8300))) (let ((m (modulo large-mod 19))) (zero? (bitwise-and (* m #x1b8bead3) (* m #x4d75a124) #x4280082b))) (let ((m (modulo large-mod 17))) (zero? (bitwise-and (* m #x6736f323) (* m #x9b1d499) #xc0000300))) (let ((m (modulo large-mod 11))) (zero? (bitwise-and (* m #xabf1a3a7) (* m #x2612bf93) #x45854000))) (let ((root (isqrt n))) (if (= (* root root) n) root #f))))))) (display (square? 152415787532388367504942236884722755800955129)) (newline)