amalloy

Implementing complex numbers and FFT with just datatypes (no floats)

In this article, I'll explain why implementing numbers with just algebraic datatypes is desirable. I'll then talk about common implementations of FFT (Fast Fourier Transform) and why they hide inherent inefficiencies. I'll then show how to implement integers and complex numbers with just algebraic datatypes, in a way that is extremely simple and elegant. I'll conclude by deriving a pure functional implementation of complex FFT with just datatypes, no floats.

amalloy

function savePiecePositions()
    savedPieces = {}
    for _, obj in ipairs(getObjectsWithTag("Resettable")) do
        savedPieces[obj.getGUID()] = {
            data=obj.getData(),
            position=obj.getPosition(),
            rotation=obj.getRotation(),
        }
    end
end

amalloy

-- seems fairly straightforward: wnumIncreasingDiffsOfSize is some loop with y_a2nf as iterator index.
-- it checks whether the loop should stop; if not, it calls get a couple times, compares the results, and updates sum

-- RHS size: {terms: 101, types: 31, coercions: 0, joins: 1/5}
$wnumIncreasingDiffsOfSize
  = \ ww_s3K3 ww1_s3Ka ww2_s3Kf ww3_s3Ki ->
      let { y_a2nf = -# ww2_s3Kf ww_s3K3 } in
      case ># ww1_s3Ka y_a2nf of {
        __DEFAULT ->
          let { wild_a2n2 = I# ww2_s3Kf } in

amalloy

(defn stratify [coll]
  (z/root (reduce (fn [loc x]
                    (let [prev (z/node loc)]
                      (cond (= x prev) (-> loc (z/insert-right x) (z/right))
                            (> x prev) (-> loc (z/insert-right [x]) (z/right) (z/down))
                            :else (-> loc (z/up) (z/insert-right x) (z/right)))))
                  (-> (z/vector-zip [(first coll)])
                      (z/down))
                  (rest coll))))

amalloy

(defn stratify [coll]
  (:ret ((fn step [coll]
           (loop [ret [], coll coll]
             (if (empty? coll)
               {:ret ret :remainder nil}
               (let [x (first coll)
                     [same different] (split-with #(= % x) coll)
                     so-far (into ret same)
                     pending (seq different)]
                 (cond (nil? pending) {:ret so-far :remainder nil}

amalloy

import Data.Semigroup (stimes)

newtype Product = Product Integer

instance Semigroup Product where
  Product x <> Product y = Product $ x * y

instance Monoid Product where
  mempty = Product 1

amalloy

$ touch tmp

$ git hash-object tmp
e69de29bb2d1d6434b8b29ae775ad8c2e48c5391

$ chmod +x tmp

$ git hash-object tmp
e69de29bb2d1d6434b8b29ae775ad8c2e48c5391

amalloy

;; consumes all memory
((fn foo [s]
   ((^:once fn bar []
            (last s))))
 (range))

;; bytecode inspection summary: foo clears its local copy of s, but bar never clears its closed-over copy

;; disassembly of bar:
user> (println (disassemble-str 

amalloy

`!lg * recent / won` produces 2 queries, and divides one by the other. Here's the numerator:

explain analyze SELECT COUNT(*) AS fieldcount FROM logrecord 
                INNER JOIN l_ktyp ON logrecord.ktyp_id = l_ktyp.id 
                INNER JOIN l_cversion ON logrecord.cv_id = l_cversion.id
                WHERE ((l_ktyp.ktyp = 'winning') AND (l_cversion.cvnum >= '2200099000000'::bigint));

 Aggregate  (cost=446001.87..446001.88 rows=1 width=8) (actual time=9661.391..96
61.391 rows=1 loops=1)
   ->  Hash Join  (cost=4909.80..445813.68 rows=75274 width=0) (actual time=1912

amalloy

query plan for `lm *`:                                   
                                   
                                   
------------------------------------------------------------------------------------------------------------------------------------------------------
 Finalize Aggregate  (cost=2406794.84..2406794.85 rows=1 width=8) (actual time=47772.901..47772.901 rows=1 loops=1)
   ->  Gather  (cost=2406794.62..2406794.83 rows=2 width=8) (actual time=47772.832..47774.309 rows=3 loops=1)
         Workers Planned: 2
         Workers Launched: 2
         ->  Partial Aggregate  (cost=2405794.62..2405794.63 rows=1 width=8) (actual time=47769.615..47769.615 rows=1 loops=3)
               ->  Parallel Seq Scan on milestone  (cost=0.00..2356329.70 rows=19785970 width=0) (actual time=0.121..45652.718 rows=15828777 loops=3)