; 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 (let ((p (- (expt 2 89) 1)) (q (- (expt 2 89) 21))) (square? (* p q))))
(newline)
(display (let ((p (- (expt 2 89) 1))) (square? (* p p))))
(newline)