tabidots

(defn babylonian-root
  "High-precision BigDecimal nth-root using the Babylonian algorithm,
  with a close initial approximation for ridiculously fast convergence."
  [n root]
  (let [eps 0.000000000000000000000000000000000000000001M]
    (loop [t (bigdec (tower/expt n (/ root)))] ;; rough initial approx
      (let [ts  (repeat (- root 1) t)
            nxt (with-precision 100 (-> (/ n (reduce *' ts))
                                        (+ (reduce +' ts))
                                        (/ root)))]

tabidots

(defn spf-sieve
  [n]
  ;; Adapted from https://stackoverflow.com/a/48137788/4210855
  (let [^ints sieve (int-array n (range n))
        upper-bound (h/isqrt n)]
    (loop [p 2] ;; p's are the bases
      (if (> p upper-bound) sieve
        (do
          (when (= p (aget sieve p))
            (loop [i (* 2 p)] ;; i's are the multiples of p

tabidots

(ns numthy.factorization
  (:require [clojure.math.numeric-tower :as tower]
            [numthy.helpers :as h]))

(defn spf-sieve
  [n]
  ;; Adapted from https://stackoverflow.com/a/48137788/4210855
  (let [^ints sieve (int-array n (range n))
        upper-bound (h/isqrt n)]
    (loop [p 2] ;; p's are the bases

tabidots

;; Hard-coded values for c, m, x here to debug the code and compare performance vs. Python implementation
;; Performance is VERY poor (~4 min). This is the fifth rewrite, and the most functional 
;; (imperative attempts did not fare much better, and were incredibly ugly).
;; However, with the same seed values, this does perform the algorithm correctly 
;; (that is, identically to the fast Python implementation below), finding a factor at some point in the loop
;; between r = 1048576 and r = 2097152.

;; With reference to Brent's paper "An Improved Monte Carlo Factorization Algorithm
;; https://maths-people.anu.edu.au/~brent/pd/rpb051i.pdf

tabidots

(defn rand-approx-product-subset
  "Generates a randomized subset of a coll of integers whose product has a chance of
  approximating `goal`."
  [goal coll]
  (let [midrange      (-> (apply max coll) (- (apply min coll)) (/ 2.0))
        tipping-point (/ goal (Math/sqrt midrange))]
    (loop [product 1N coll' (shuffle coll) subset []]
      (if (> product tipping-point) subset
        (let [x (first coll')]
          (recur (*' product x) (rest coll') (conj subset x)))))))

tabidots

(defn ordered-matches
  [s1 s2]
  (let [enumerate   (fn [coll] (map-indexed vector coll))
        floor       (fn [x] (Math/floor x)) ; cljs: (.floor js/Math x)
        window-span (-> (max (count s1) (count s2))
                        (/ 2) floor dec)]
    (remove nil?
      (for [[i top] (enumerate s1)] ; cannot be put into a single for-comprehension
        (first
          (for [[j bottom] (enumerate s2)