

        <cite>Ben</cite>
      <time>0:00</time>
      <p>
          And   he   asked   the   question   of   like,   you   know,   does   C   have   a   good   way   to   uh   to   take   an   item   out   of   a   sequence   and   put   it   back   somewhere   else? That   was   literally   a   question   I&#39;m   like,   I   can&#39;t   believe   this   has   landed   in   my   lap   on   my   screen.   I&#39;m   like,   I   can&#39;t   believe   I&#39;m   about   to   say   this.
      </p>

        <cite>Sean Parent</cite>
      <time>0:18</time>
      <p>
          That&#39;s   a   rotate.   And   so   so   it&#39;s   literally   the   Euclid&#39;s   GCD,   it&#39;s   just   subtraction   is   swap   ranges.   And   then   you   just   run   Euclid&#39;s   algorithm,   which   is   very   beautiful,   right?   It&#39;s   this   beautiful   connection   between   a   mathematic   notation   and   this   and   this   operation.
      </p>

        <cite>Conor</cite>
      <time>0:47</time>
      <p>
          Welcome   to   ADSP   the   podcast,   episode   202,   recorded   on   September   26,   2024.   My   name   is   Connor,   and   today   with   my   co-host   Ben,   we   chat   with   Sean   Parent   about   Stood   Rotate,   GCD,   elements   of   programming   from   mathematics   to   generic   programming   and   more.   Alrighty,   we   are,   I   believe,   recording   now   episode   202.   I   think   I   failed   to   mention   it   on   episode   201,   but   I&#39;m   considering   this   season   two.   Season   one   was   a   reasonable   200   episodes,   and   now   we&#39;ve   started   season   two   after   almost   four   years,   and   we&#39;re   gonna   be   we&#39;re   gonna   be   trying   some   different   things,   you   know.   After   four   years,   we   gotta   we   gotta   change   things   up   a   bit.   But   we   had   episode   199.   It   was   entitled   Stood   Rotate,   and   Bryce   and   I   fumbled   our   way   through   trying   to   talk   about   how   would   you   implement   uh   rotate   and   missed   the   fact   that   the   number   of   operations   on   the   linear   algorithm   is   basically   half   the   length.   Realized   that   with   like   five   minutes   left   in   the   podcast   recording,   we   apologized   to   Sean,   understanding   that   if   he   did   listen   to   this,   he   would   be   disappointed.   Uh,   I   believe   uh   you   were   disappointed,   but   you   accepted   our   apology   on   Twitter,   and   uh   you   were   one   of   three   people.   So   you   mess   it,   you   tweeted   Sean,   saying   that   uh   at   least   you   apologized.   In   STL,   there   are   three   algorithms   used   for   rotate:   Fletcher   and   Silver   for   random   access,   three   reverses   for   bidirectional,   the   one   we   discussed,   and   then   Grease   and   Mills   for   forward   iterators.   And   you   mentioned   that   Grease   and   Mills   is   Euclid&#39;s   subtractive   GCD   algorithm.   Ben   DM&#39;d   me   and   uh   mentioned   the   same   thing   I   believe   about   the   forward   iterator   algorithm,   and   then   Tristan   also   tweeted   and   I   think   linked   to   a   paper   talking   about   the   forward   iterator   version.   So   now   I&#39;ve   we&#39;ve   brought   on   two   of   the   three   people   that   messaged   me.   Tristan,   don&#39;t   worry.   Uh,   we   have,   I   think,   lined   up.   We&#39;re   gonna   bring   him   back   on   to   talk   about   the   sort   of   changes   and   recent   updates   to   Flux.   We   were   actually   supposed   to   record   when   I   was   in   London   uh   back   in   August,   but   we   ended   up   meeting   up   at   his   local   pub   in   oh   my   goodness,   I&#39;m   gonna   forget   the   name   of   the   town   that   is   just   on   the   outside   of   London.   Uh,   but   we   met   up   twice   actually,   and   I   got   to   see   we   actually   went   on   a   bird   walk.   If   you   can   guess   at   it,   I   might   be   able   to   recognize   it.   If   you&#39;ve   got   like   Oh,   it&#39;s   it&#39;s   I   believe   it&#39;s   Rick   Rickmansworth.   Rickmansworth,   I   believe.
      </p>

        <cite>Ben</cite>
      <time>3:09</time>
      <p>
          Okay,   yeah.
      </p>

        <cite>Conor</cite>
      <time>3:10</time>
      <p>
          That&#39;s   it.   That&#39;ll   be   it.   Which   is,   yeah.   Not   in   London,   but   adjacent   to   London.
      </p>

        <cite>Ben</cite>
      <time>3:15</time>
      <p>
          It&#39;s   slightly   up   the   A40,   I&#39;m   gonna   say,   something   like   that.   The   M40.   It&#39;s   so   it&#39;s   uh   north   northwest.
      </p>

        <cite>Conor</cite>
      <time>3:23</time>
      <p>
          Yes,   I   subwayed,   and   uh   we   can   actually   blame   Taylor   Swift   for   the   reason   that   we   didn&#39;t   record   because   she   was   performing   at   Wembley   Stadium,   and   I   ended   up   getting   out   there   like   an   hour   later   because   of   all   the   Swift   fans   that   were   taking   the   underground.   And   uh   so   we&#39;ll   blame   Taylor   Swift.   Uh,   and   I   apologize   to   any   listeners   that   are   big   fans.   Uh,   but   it   is   the   case   that   her   concert   and   her   fans   delayed   me   getting   out   there.   Anyways,   I&#39;m   gonna   throw   it   over   to   you   two   now.   I&#39;m   not   sure   if   Sean,   you   want   to   start   first   um   because   I   did   not   go   ahead   and   do   any   research   on   these   other   uh   implementations.   I   figured   I   would   just   learn   via   inviting   you   on.   And   uh   yeah,   let   me   get   maybe   your   thoughts   while   you   were   listening   to   it.   How   upset   were   you?   And   uh   once   once   again,   Bryce   and   I   both   apologize.
      </p>

        <cite>Sean Parent</cite>
      <time>4:12</time>
      <p>
          Uh   yeah,   well,   uh   it   was   annoying   because   I   think   both   of   you   guys   probably   have   elements   of   programming   and   all   these   algorithms   are   covered   in   in   EOP.   Uh   uh   so   you   could   have   just   like   cracked   the   book   and   taken   a   look.   The   other   piece   of   it   is   is   anytime   you&#39;re   dealing   with   uh   a   permutation   algorithm,   uh,   every   permutation   algorithm   uh   decomposes   into   a   set   of   cycles.   And   what   that   means   is   if   you   think   about,   I   can   you   know   remove   one   element   and   then   I   if   I   know   what   piece   goes   into   that   element,   I   move   that   piece   into   the   hole,   and   that   leaves   another   hole,   and   so   something   moves   into   that   hole,   and   it   keeps   going   until   the   the   the   one   element   that   I   that   I   took   out   goes   into   the   hole.   And   so   that   creates   a   cycle   going   around.   And   so   kind   of   the   worst   case   is   is   uh   uh   if   you&#39;re   doing   a   reverse   for   the   number   of   cycles,   because   you&#39;re   gonna   have   every   swap   is   a   is   a   trivial   cycle   of   of   two   elements.   Right.   It   turns   out   that   when   you&#39;re   doing   a   rotate,   that   the   number   of   cycles   you   have   is   the   the   GCD   of   the   length   of   the   two   halves.   Right?   So   that&#39;s   how   the   cycles   decompose.   That&#39;s   why   you   have   the   complexity   of   the   random   access   algorithm,   that&#39;s   why   the   complexity   of   that   is   driven   by   GCD.   And   so,   you   know,   your   worst   case   then   is   where   the   ranges   are   are   equal   length,   in   which   case   rotate   is   just   a   swap   ranges,   and   every   cycle   is   just   a   swap.   Uh   but   that   algorithm,   if   you&#39;re   given   random   access,   minimizes   the   number   of   moves.   It   goes   through   each   cycle,   and   so   every   element   is   is   only   is   only   moved   into   its   final   position.   Uh   so   you&#39;re   going   to   have   uh   if   you   have   n   elements,   you&#39;re   gonna   have   n   moves   plus   one   for   each   cycle.   So   it&#39;s   going   to   be   n   moves   plus   gcd   of   of   nm   moves.   Uh   uh.   So   that&#39;s   how   how   you   can   do   that.   Now,   the   interesting   thing   is   is   the   complexity   of   the   forward   iterator   case   and   the   complexity   of   the   three   reverses   case   is   is   the   same   number   of   moves.
      </p>

        <cite>Ben</cite>
      <time>6:31</time>
      <p>
          Just   cla   clarification   there,   Sean.   Do   you   mean   that   they&#39;re   the   same   number   of   moves   as   each   other   or   as   the   random   access   case?
      </p>

        <cite>Sean Parent</cite>
      <time>6:39</time>
      <p>
          Uh   uh   as   each   other.   So   it&#39;s   um   uh   uh   which   is   gonna   be   more   because   you&#39;re   you&#39;re   breaking   it   down   all   into   all   into   swaps.   And   so   if   you&#39;re   doing   three   reverses,   right,   then   then   you&#39;re   going   to   to   uh   you&#39;re   gonna   reverse   each   half   or   each   each   segment   and   then   reverse   the   whole.   And   and   so   each   of   those   uh   uh   reverses   is   n   over   two   swaps,   and   so   you&#39;re   gonna   have   you   know   n   over   two   plus   n   plus   m   swaps.   Uh   uh   when   you&#39;re   doing   it   with   uh   uh   uh   forward   iterators,   you&#39;re   swapping   elements.   How   to   describe   this?   So   you&#39;re   basically   gonna   swap   ranges,   uh   but   the   two   are   equal   or   unequal   halves,   and   so   you&#39;re   going   to   be   swapping   ranges   up   until   you   hit   the   the   midpoint,   and   then   that   leaves   you   a   new   piece,   and   then   you&#39;re   gonna   swap   that   piece,   and   then   swap   that   piece.   Okay,   and   so   you&#39;re   gonna   end   up   swapping   every   element,   uh   calling   swap   for   every   element   once.   And   so   that&#39;s   the   that&#39;s   the   same   as   the   the   three   rotates.   Now   I   suspect,   but   I   haven&#39;t   haven&#39;t   tested   it,   that   uh   the   forward   algorithm   these   days   probably   wins.   I   don&#39;t   know   that   we   could   make   the   change   in   STL   because   we   have   the   guarantees   on   number   of   moves   for   the   random   for   the   random   access   case.   But   just   because   of   locality   and   caches,   uh   uh   it&#39;s   much   faster   to   iterate   through   a   sequence   always   going   forward.   Always   moving   forward.   Uh   uh   and   so   almost   positive   that   that   always   wins   over   three   reverses,   which   is   the   the   bidirectional   iterator   case.   And   and   I   would   be   very   surprised   if   if   you   have   a   low-cost   move,   uh   uh   if   it   didn&#39;t   win   even   over   the   random   access   case,   which   would   have   fewer   move   operations,   uh   uh,   but   horrible   locality,   because   you&#39;re   you&#39;re   tracing   cycles   all   all   through   your   sequence.   Um,   so   even   worse   locality   than   the   than   the   random   access   case.   For   something   like   thrust,   which   apparently   is   missing   rotate,   which   is   a   crime.
      </p>

        <cite>Ben</cite>
      <time>8:58</time>
      <p>
          How   is   it   possible   to   miss   rotate?   It&#39;s   a   fundamental   building   block,   right?   If   you&#39;re   missing   rotate,   how   are   you   implementing   a   bunch   of   stuff   which   depends   on   rotate?
      </p>

        <cite>Conor</cite>
      <time>9:07</time>
      <p>
          In   in   defense   of   the   the   good   folks   at   NVIDIA,   uh   David   Olsen,   who   we   interviewed   on   that   CPP   North   episode   for   the   first   10   or   12   minutes,   uh,   he   pinged   me   after   the   episode   went   live   and   said,   uh,   this   is   on   a   uh   a   GitHub   issue   that   was   filed   in   like   2012   or   something   like   that,   when   Thrust,   like   in   the   early   days,   and   then   they   pointed   out   that   these   algorithms   are   missing   and   we   should   add   them.   And   it&#39;s   actually   because   of   that,   because   uh   the   stdd.par   MVC   compiler   that   implements,   you   know,   you&#39;d   write   C   and   can   easily   parallelize   it   by   just   passing   a   flag.   There&#39;s   a   couple   algorithms   that   actually   aren&#39;t   supported,   and   rotate   is   one   of   them   because   thrust   is   what   it   lowers   down   onto.   Um   but,   anyways,   we   we&#39;ll   we&#39;re   getting   to   it.   Bryce   and   I,   we&#39;re   gonna   fix   it.   Uh,   or   by   we,   I   mean   probably,   you   know,   David   and   friends.   But   uh,   you   know,   in   it   by   episode   400,   this   is   an   ADSP   promise.   You   know,   another   four   years   from   now,   there&#39;ll   definitely   be   a   thrust   rotate.
      </p>

        <cite>Ben</cite>
      <time>10:08</time>
      <p>
          So   rotate   I   was   gonna   say   ro   rotate   is   one   of   these   algorithms   that   really   has   um   a   kind   of   uh   people   experience   a   semantic   gap.   And   it   in   in   general,   you   know,   because   in   C   the   algorithms   are   called   what   they   do   at   a   very   low   level   rather   than   what   they   do   at   a   domain   level,   right?   So   so   like   partial   sort   is   not   called   top   N,   for   example,   right?   And   rotate   is   one   of   these   others   that   that   people   see   the   explanation   of   what   it   does   and   they   go   away   and   they   think,   well,   I   don&#39;t   ever   do   that   in   my   code.   Um   and   and   getting   to   the   realization   that   yes,   we   actually   do   that   all   the   time   is   one   of   the   reasons   why   you   know   C   seasoning   was   such   an   eye-opening   moment   for   many   folks.   And   and   come   on,   your   talks   about   algorithm   intuition   similarly.   Um   the   funniest   thing   that   ever   happened   to   me   on   Twitter   was   where   one   of   my   friends,   it   was   uh   Alan   Wolfe,   who&#39;s   on   graphics   Twitter,   and   and   uh   he   was   I   we   he   and   I   used   to   work   together,   and   he   asked   the   question   of   like,   you   know,   does   C   have   a   good   way   to   uh   to   take   an   item   out   of   a   sequence   and   put   it   back   somewhere   else? That   was   literally   a   question   I&#39;m   like,   I   can&#39;t   believe   this   has   landed   in   my   lap   on   my   screen.   I&#39;m   like,   I   can&#39;t   believe   I&#39;m   about   to   say   this.   That&#39;s   a   rotate.
      </p>

        <cite>Sean Parent</cite>
      <time>11:33</time>
      <p>
          Yeah,   that&#39;s   right.   You   just   answer   that   one   with   a   link   to   uh   Connor&#39;s   cut   of   my   uh   seasoning   talk.   Which   the   seasoning   talk   is   10   years   old   now,   so   I   can&#39;t   believe   we&#39;re   still   talking   about   it.   Uh   yeah,   but   it   is   a   fundamental   rotate.   And   if   you   look   at   at   uh   you   know   Connor&#39;s   an   array   programming   guy,   and   uh   uh   uh   rotate,   you   know,   has   its   own   operator   in   APL,   and   it&#39;s   uh   it   is   a   very   a   very   fundamental   algorithm   and   building   block.   So   it   definitely   deserves   to   be   in   thrust.   Uh   you   know,   the   interesting   thing   is   is   is   like   the   the   three   reverses   is   probably   the   most   trivially   parallelizable   because   reverse   itself,   all   of   your   cycles   are   independent,   so   you   can   run   all   of   those,   you   can   chunk   up   those   cycles   however   you   want   and   run   them   all   independently.   I   think   the   forward   iterator   case   to   run   in   parallel   would   require   a   little   more   thought,   but   again,   it   decomposes   all   into   swaps.   So   so   I   think   you   could   break   it   up,   break   it   up   pretty   well.   You   know,   I&#39;ve   never   attempted   it,   but   uh   I   think   doing   a   fast   parallel   uh   uh   uh   rotate   is   is   interesting.
      </p>

        <cite>Conor</cite>
      <time>12:45</time>
      <p>
          Is   is   that   true   about   the   the   three   reverse   implementation?   Because   you   can&#39;t   do   the   You   do   the   two,   you   know,   N   over   two   or   wherever   your   midpoint   is.   You   do   those   two   reverses,   but   then   the   final   reverse   on   the   whole   sequence,   isn&#39;t   that   dependent   on   the   previous   two?
      </p>

        <cite>Sean Parent</cite>
      <time>13:04</time>
      <p>
          Well   yeah,   but   it&#39;s   it&#39;s   not   that   you   do   like   the   first   two   re   well,   you   do   do   the   first   two   reverses,   you   do   them   in   parallel,   but   it&#39;s   not   the   fact   that   you   can   do   a   re   uh   that   you   can   do   those   two   reverses   simultaneously.   It&#39;s   that   an   individual   reverse   has   no   there&#39;s   no   dependency   between   each   cycle.   So   you   can   break   that   in   and   do   it   on   a   thousand   chords.   It&#39;s   data   parallel.
      </p>

        <cite>Conor</cite>
      <time>13:29</time>
      <p>
          Right.   It   it   doesn&#39;t   suffer   from   the   communication   issue   that   scanned,   or   suffers   the   wrong   word,   but   it   doesn&#39;t   have   that   property   of   a   scan   that   you&#39;re   constantly   needing   to   refer   back   and   figure   out   a   way   to   propagate   that   information.   Reverse   doesn&#39;t   have   that.
      </p>

        <cite>Ben</cite>
      <time>13:41</time>
      <p>
          Every   swap   is   data   parallel   with   every   other   swap.   Right.   Right.
      </p>

        <cite>Sean Parent</cite>
      <time>13:45</time>
      <p>
          The   random   access   algorithm,   minimizing   the   number   of   moves   in   parallel,   gets   more   challenging   because   you   need   to   you   need   to   identify   the   the   start   points   of   all   of   your   cycles.   And   then   in   theory   you   could   run   each   of   those   cycles   in   parallel.   But   again,   I&#39;m   not   sure   if   the   if   the   memory   access   patterns   would   kill   the   gains   you&#39;d   you&#39;d   get   off   of   that.   Uh   the   other   thing   is   you   in   some   cases   you&#39;re   gonna   run   into   the   case   where   where   the   uh   uh   the   number   of   cycles   is   one.   And   so   in   which   case   you   can&#39;t   parallelize   it.   You&#39;ve   gotta   you&#39;ve   gotta   run   through   the   whole   thing.   At   least   I   don&#39;t   know   of   a   way   to   parallelize   that.   So   it&#39;s   interesting.   Again,   my   intuition   says   that   the   forward   algorithm   probably   probably   wins   in   the   parallel   case,   probably   wins   in   all   cases.   Uh,   but   that&#39;s   without   you   know,   you   have   to   implement   them   all   in   benchmark   it,   right?   I   mean,   machines   these   days   are   are   nuts   for   breaking   intuition.
      </p>

        <cite>Ben</cite>
      <time>14:48</time>
      <p>
          So   I   had   a   similar   experience   when   I   was   listening   to   the   episode.   I   was   listening   and   I   thought,   okay,   well,   they&#39;re   explaining   the   hand   flipping   algorithm.   Any   minute   now,   they&#39;re   gonna   explain   how   the   Ford   iterator   algorithm   is   basically   a   GCD   algorithm,   and   they&#39;re   gonna   explain   how   that   works.   And   then,   you   know,   then   I   noticed   that   it   was   at   like   28   minutes   of   30   in   the   episode,   and   I&#39;m   like,   maybe   they&#39;re   not   gonna   get   to   it.   Right.
      </p>

        <cite>Sean Parent</cite>
      <time>15:14</time>
      <p>
          You   know,   for   the   listener,   if   you&#39;re   having   trouble   viewing   why   rotate   is   GCD,   if   uh   uh   well,   first   GCD   is   greatest   common   divisor,   and   Euclid&#39;s   algorithm   for   greatest   common   divisor   is   you   subtract   the   smaller   number   from   the   bigger   number.   If   the   uh   result   is   now   smaller,   then   you   flip   the   two   and   you   just   keep   going.   So   it&#39;s   just   iterative   subtraction,   right?   Until   you   until   the   parts   are   equal   size   and   then   and   then   you   stop.   Uh   and   so   if   you   think   of   uh   swap   ranges   as   your   subtraction   operation,   uh   then   you   can   say,   okay,   I&#39;ve   got   two   unequal   size   sequences,   and   I   can   swap   ranges,   which   will   stop   when   I   hit   the   end   of   the   shorter   segment.   And   so   that&#39;s   subtracting   the   shorter   segment   from   the   longer   segment.   Okay,   and   so   now   what   I   end   up   with   after   I   do   that   is   I&#39;m   done   with   the   beginning   up   to   the   point   where   I   stopped,   and   now   I   have   a   piece   left   of   which   I   stopped   somewhere   halfway   through   there.   And   so   that   gives   me   my   three   points,   my   three   numbers   to   continue   my   sub   my   subtraction.   And   so   so   it&#39;s   literally   the   Euclid&#39;s   GCD,   it&#39;s   just   subtraction   is   swap   ranges.   And   then   you   just   want   Euclid&#39;s   algorithm,   which   is   very   beautiful,   right?   It&#39;s   this   beautiful   connection   between   a   mathematic   notation   and   this   and   this   operation.   And   that&#39;s   why   GCD   keeps   popping   out,   right?   Right,   right.   The   number   of   cycles   is   G   C   D   number   of   cycles,   and   and   and   so   the   complexity   of   the   random   access   algorithm   gets   described   in   G   C   D   because   there&#39;s   no   more   minimal   way   to   do   it.
      </p>

        <cite>Ben</cite>
      <time>17:06</time>
      <p>
          Yeah,   so   uh   I   always   think   of   algorithms   recursively.   I   think   that&#39;s   at   least   the   right   way   to   think   about   algorithms,   you   know,   when   you   code   them,   you   can   remove   the   recursion.   But   to   me,   the   right   way   to   think   about   algorithms   is   recursively.   And   that   that&#39;s   exactly   what   you   just   said,   Short.   Like   like   what   do   you   do   with   rotate?   Well,   you   put   you   put   the   things   at   the   beginning   of   the   range   first,   right?   You   you   rotate   something   into   the   beginning   of   the   range,   and   then   it   stops   at   some   point,   and   then   what   are   you   left   with?   A   new   rotate   effectively   that   is   smaller   than   the   old   one.   And   so   you   recursively   that   that   works,   and   that   is   GCD,   as   you   said,   right?
      </p>

        <cite>Conor</cite>
      <time>17:38</time>
      <p>
          So   this   is,   I   don&#39;t   know,   I   feel   bad   admitting   this   on   air,   especially   after   having   had   Zach   on.   Because   I   think   actually   there&#39;s   another   thing   to   point   out.   We   have   our   two   most   frequent   guests,   so   you   guys   are   just   putting   uh   you   know   more   distance   on   the   rest   of   our   guests.   But   uh   we   had   Zach   on,   I   think   he&#39;s   up   there   for   a   number   of   episodes,   um,   and   he   said   the   way   to   do   it   is   to   read   EOP,   Elements   of   Programming,   available   free   online,   link   in   the   show   notes   three   times.   You   you   you   know,   you   don&#39;t   skim   through   it,   but   you   read   through   it   quickly   without   stopping   to   digest   everything,   and   that   doesn&#39;t   take   too   long.   Then   you   go   through   a   second   time,   and   that&#39;s   the   one   where   you   treat   it   like   a   textbook,   you   know,   work   through   things,   try   to   understand   them,   and   then   you   read   it   a   third   and   final   time   at   the   same   speed   you   read   it   the   first   time.   I   have   not   actually   fully   read   EOP.   I&#39;m   not   sure   if   uh   you   know   Sean&#39;s   heart   is   breaking   right   now,   but   there&#39;s   there&#39;s   two   things   that   have   been   high   on   my   list   of   things   to   do.   I   know   uh   both   of   you   have   done   them.   Uh   obviously   Sean&#39;s   read   EOP   and   so   has   Ben.   But   also   too,   Ben,   you   have   watched   the   what   is   it?   It&#39;s   the   four   algorithmic   journeys   that   was   that   came   out   of   A9.
      </p>

        <cite>Ben</cite>
      <time>18:44</time>
      <p>
          Is   that   the   is   that   the   correct   title   of   the   uh   I   think   yes,   it&#39;s   algorithmic   journeys.   Um   yeah,   there&#39;s   a   hundred   hours   plus   of   A9   video   content.   Presentations   from   Alex   Stepanov   within   Amazon   A9.   They   are   I   would   highly   recommend   them   to   everyone.   They   those   algorithmic   journeys   videos   are   the   video   version,   if   you   like,   of   the   second   book,   which   is   um   from   mathematics   to   generic   programming.   And   that   book   in   particular   explores   G   C   D   a   lot.   Yes.
      </p>

        <cite>Sean Parent</cite>
      <time>19:20</time>
      <p>
          GCD   comes   up   repeatedly   in   it.
      </p>

        <cite>Conor</cite>
      <time>19:22</time>
      <p>
          And   so   and   Sean,   I   know   that   you   gave,   if   not   attended,   some   of   those   I   think   you   I   definitely   know   you   were   a   guest   speaker,   I   think,   as   one   of   those   talks.   That   is   programming   conversations,   lecture   five,   part   two.
      </p>

        <cite>Ben</cite>
      <time>19:37</time>
      <p>
          Yes.   I&#39;m   not   sure   if   it&#39;s   part   one   or   two,   maybe   both.
      </p>

        <cite>Conor</cite>
      <time>19:40</time>
      <p>
          It&#39;s   the   one   that   you   you   give   the   extended   version   of   the   Google   Rotate   uh   story,   I   believe,   in   that   edition,   which   I   think   we&#39;ve   talked   about   on   this   podcast,   but   uh   I&#39;ve   never   said   that   I   I   actually   haven&#39;t   watched   all   of   them,   even   though   for   years   now   I&#39;ve   had   it   linked   as   a   bookmark.   But   the   problem   is   that   my   curiosity   is   is   too   vast   that   I   so   I&#39;ve   seen   little   pieces,   I&#39;ve   definitely   seen   the   um   2002   is   it,   Stepanov   talk   that   I&#39;ve   cited   in   a   couple,   which   I   think   he   came   and   gave   at   Adobe.   How   many   of   those   did   you   see   that   were   given   at   A9   slash?   I   assume   you   just   know   most   of   that   stuff,   probably   from   conversations   directly   with   Alex.
      </p>

        <cite>Sean Parent</cite>
      <time>20:16</time>
      <p>
          Uh   well,   yeah,   so   I   I   don&#39;t   know.   I   attended   a   few   of   them.   I   watched,   I   think   all   of   them   online,   you   know,   plus   Alex   and   I   worked   largely   in   the   same   room   together   for   eight   years,   so   I&#39;m   I&#39;m   I&#39;m   pretty   familiar   with   most   of   most   of   his   material   there.   Uh   uh   I   did   link   in   the   show   notes   to   uh   uh   uh   uh   Alex&#39;s   talk   on,   or   I   link   to   it   on   Twitter,   which   that   will   be   in   the   show   notes,   uh,   to   my   favorite   talk   of   all   time,   which   is   which   is   Alex,   Alex&#39;s   G   C   D   talk.   Uh   it&#39;s   the   history   of   GCD   the   last   2500   years,   and   that&#39;s   one   of   the   journeys   in   the   from   mathematics   to   generic   programming.   Which   I   love   that   title,   and   Alex   views   it   as   generic   programming   is   is   is   the   next   step   in   mathematics,   is   the   is   the   arc   there.   That   mathematicians   have   been   working   on   algorithms   and   how   you   solve   problems   for   centuries,   and   kind   of   moving   that   into   the   computer   domain   as   part   of   it,   and   and   mathematics   we   think   of   as   being   relatively   abstract,   and   generic   programming   is   carrying   those   mathematical   abstractions   into   into   the   programming   space.   You   know,   that   book   in   particular,   for   for   the   listener   and   for   you,   Connor,   uh   pick   up   a   copy,   read   it.   Uh   uh   that&#39;s   compared   to   EOP,   it&#39;s   a   much   easier   read.   It&#39;s   not   a   textbook,   it&#39;s   it&#39;s   it&#39;s   stories.   And   and   so   it&#39;s   it&#39;s   his   it&#39;s   a   lot   of   history,   it&#39;s   a   little   bit   of   math,   uh,   and   a   little   bit   of   programming,   and   and   they&#39;re   stories.   They&#39;re   they&#39;re   tracing   the   origin   of   fundamental   algorithms   uh   through   history   and   looking   at   the   mathematicians.   Who   extended   or   improved   on   the   algorithm   through   history   and   what   their   motivation   was,   why   they   were   dealing   with   that   particular   algorithm   at   that   particular   time   in   history,   and   you   know   what   their   realization   was,   and   then   what   the   ongoing   ramifications   of   that   are.   So   it&#39;s   interesting.   And   even   things   like   uh   uh   GCD,   there   are   still   open   problems   in   mathematics.
      </p>

        <cite>Ben</cite>
      <time>22:25</time>
      <p>
          Well,   and   I&#39;m   blanking   on   the   name   now,   but   there   was   the   the   Israeli   researcher   in   the   late   60s   or   early   70s   who   developed   a   version   of   GCD   through   necessity,   which   I&#39;m   blanking   on   this   name.
      </p>

        <cite>Sean Parent</cite>
      <time>22:38</time>
      <p>
          Yeah,   uh   Joseph   Stein.   Stein,   yes,   the   Stein   G   C   D   So   it&#39;s   a   Stein   algorithm   for   G   C   D   and   it&#39;s   a   binary   GCD.   So   it&#39;s   it&#39;s   what   you   you   know,   if   you   call   a   G   C   D   on   your   computer,   it&#39;s   probably   what&#39;s   executing   on   your   computer.   Uh   uh   the   interesting   thing   is   the   Euclidean   algorithm   uh   defines   what&#39;s   known   as   the   Euclidean   domain,   which   is   uh   for   any   kind   of   abstract   number   system,   uh   uh   uh   if   if   GCD   works,   if   the   GCD   algorithm   terminates,   this   this   incremental   subtraction,   if   you   always   end   up   at   zero,   basically,   by   doing   by   doing   incremental   subtraction,   uh   uh,   then   that   numeric   system   is   in   the   Euclidean   domain.   And   so   so   you   you   know,   so   the   interesting   thing   is   that   Stein&#39;s   algorithm   does   not   appear   to   be   the   numbers   that   for   which   the   Stein   algorithm   works   don&#39;t   appear   to   be   exactly   the   same   set   of   numbers   for   which   the   Euclidean   algorithm   works.   And   so   the   open   question   is   is   the   Stein   domain   the   same   as   the   Euclidean   domain?   Is   it   a   superset   of   the   Euclidean   domain?   Is   it   a   subset   of   the   Euclidean   domain?   And   I   haven&#39;t   tracked   it   closely.   I   think   you   know   last   time   I   looked,   there   was   one   proof   of   something   that   was   in   the   Stein   domain   that   wasn&#39;t   Euclidean,   and   one   proof   of   the   opposite.   So   there&#39;s   this   section   that   there&#39;s   some   some   Venn   overlap,   uh,   but   they   both   have   have   unique   bounds.   But   over   time   there&#39;s   been   a   number   of   proofs   that   have   just   failed,   right?   Right,   they   people   have   submitted   proofs   on   that,   and   then   under   peer   review,   the   the   proofs   collapse.   Uh   so   as   far   as   I   know,   it&#39;s   still   an   open   problem.   Uh,   but   you   know,   it&#39;s   it&#39;s   it&#39;s   pretty   amazing.   And   and   because   of   Alex   bringing   all   of   this   up,   and   uh   Alex   actually   managed   to   contact   uh   uh   Joseph   Stein,   who   at   least   as   of   a   decade   ago   was   was   still   alive.   And   he   was   just   like   a   you   know   engineer   working   in   Israel   who   came   up   with   this   algorithm   and   it   got   published   and   went   everywhere,   and   he   was   completely   unaware   that   that   there   was   this   whole   branch   of   mathematics   research   that   he   triggered.
      </p>

        <cite>Conor</cite>
      <time>25:05</time>
      <p>
          So   Wow.   When   when   you   s   when   when   you   say   that   the   you   know   subset   or   superset   of   things   that   it   works   for,   I   imagine   this   doesn&#39;t   uh   impact   like   the   correctness   of   what&#39;s   happening   on   your   hardware   if   if   that&#39;s   the   algorithm   that&#39;s   taking.   Is   it   the   things   for   like   for   certain   types   that   it   it   doesn&#39;t   work?   Or   like   what   is   what   are   the   edge   cases?
      </p>

        <cite>Sean Parent</cite>
      <time>25:25</time>
      <p>
          So   so   it&#39;s   you   know   if   you   think   about   uh   number   systems   like   integers,   okay.   Both   algorithms   work   fine   for   integers.   Both   algorithms   work   fine   for   reals.
      </p>

        <cite>Ben</cite>
      <time>25:34</time>
      <p>
          And   then   you   have   things   like   polynomials   with   real   coefficients.
      </p>

        <cite>Sean Parent</cite>
      <time>25:38</time>
      <p>
          Or   or   just   complex   numbers,   or   or   okay,   so   so   that&#39;s   what   I   mean   by   different   different   types   of   numbers,   right?
      </p>

        <cite>Conor</cite>
      <time>25:48</time>
      <p>
          Right.
      </p>

        <cite>Sean Parent</cite>
      <time>25:48</time>
      <p>
          Right.   And   then   there&#39;s   an   infinite   number   of   ways   that   you   can   create   new   domains   for   numbers,   right?   There&#39;s   there&#39;s   there&#39;s   sets   of   them   that   are   useful,   but   you   can   make   up   your   own   set   of   rules,   and   that   becomes   becomes   a   a   number.   So   if   you&#39;re   dealing   much   in   the   in   the   abstract   algebra   space,   you   know,   that&#39;s   what   you&#39;re   trying   to   do.   And   the   Euclidean   domain   is   odd   in   that   the   there&#39;s   no   better   definition   than   it&#39;s   this   the   the   the   set   of   numbers   for   which   the   Euclid   algorithm   terminates.   Okay?   It&#39;s   it&#39;s   you   can   have   algorithms   that   uphold   the   the   other   axioms   of   of   Euclid&#39;s   algorithm,   but   it   but   but   there&#39;s   no   axiom   better   than   just   the   algorithm   must   terminate.
      </p>

        <cite>Ben</cite>
      <time>26:34</time>
      <p>
          Right.   So   it&#39;s   kind   of   an   extrinsic   definition.   There&#39;s   nothing   intrinsic   to   say.   It&#39;s   just   kind   of   like   the   fifth   postulate,   you   know,   it   is   because   it   is.
      </p>

        <cite>Sean Parent</cite>
      <time>26:46</time>
      <p>
          Right.   And   that   makes   it   very   difficult.   There&#39;s   no   there&#39;s   no   single   axiom   that   you   can   point   to   and   say,   oh,   so   long   as   my   number   system   satisfies   X,   then   it&#39;s   within   the   Euclidean   domain.   Because   the   definition   of   it   within   the   Euclidean   domain   is   so   long   as   Euclid&#39;s   algorithm   terminates.   Right.   And   that   gets   to   be   very   interesting   to   try   to   prove   or   disprove   for   any   two   numbers   within   a   given   domain,   does   Euclid&#39;s   algorithm   terminate   or   not?
      </p>

        <cite>Conor</cite>
      <time>27:19</time>
      <p>
          And   that&#39;s   an   open   question.
      </p>

        <cite>Sean Parent</cite>
      <time>27:20</time>
      <p>
          There&#39;s   no   general   rule   to   it.   There   are   there   are   many   proofs   from   many   different   for   many   different   domain   instances.
      </p>

        <cite>Conor</cite>
      <time>27:27</time>
      <p>
          Yes.   Be   sure   to   check   these   show   notes   either   in   your   podcast   app   or   at   adspthepodcast.com   for   links   to   anything   we   mentioned   in   today&#39;s   episode,   as   well   as   a   link   to   a   GitHub   discussion   where   you   can   leave   thoughts,   comments,   and   questions.   Thanks   for   listening.   We   hope   you   enjoyed   and   have   a   great   day.   I   am   the   anti   Bryce.   Um
      </p>