Blinder binärer Addierer

10

Stellen Sie sich vor, Sie haben zwei Boxen B(x)und B(y)jeweils ein unbekanntes Bit - 0 oder 1 - und eine Maschine F, die sie röntgen und eine dritte Box für B(x^y)( xor ) produzieren kann. Fkann auch berechnen B(x*y)( und ). Tatsächlich sind dies nur Sonderfälle des einzelnen Vorgangs, den die Maschine ausführen kann - jeweils ein inneres Produkt , das F()unten angegeben ist.

Für zwei Arrays gleicher Länge

[B(x[0]), B(x[1]), ..., B(x[n-1])]
[B(y[0]), B(y[1]), ..., B(y[n-1])]

inneres Produkt ist definiert als

B(x[0]*y[0] ^ x[1]*y[1] ^ ... ^ x[n-1]*y[n-1])

Jede “ Mittel F()können mehrere Paare von verarbeiten x[], y[]in einem Arbeitsgang. Das x[]und y[]von einem Paar muss gleich lang sein; x[]-s und y[]-s von verschiedenen Paaren müssen nicht unbedingt.

Boxen werden durch eindeutige Ganzzahl-IDs dargestellt.

Eine Implementierung des inneren Produkts in JavaScript könnte folgendermaßen aussehen

var H=[0,1];          // hidden values, indexed by boxId
function B(x) {       // seal x in a new box and return the box id
  return H.push(x)-1;
}
function F(pairs) {   // "inner product each"
  return pairs.map(function (pair) {
    var r = 0, x = pair[0], y = pair[1];
    for (var i = 0; i < x.length; i++) r ^= H[x[i]] * H[y[i]];
    return B(r);
  })
}

(Bitte übersetzen Sie das Obige in die Sprache Ihrer Wahl.)

Der Zugang zu einer F()Implementierung als geeignet für Ihre Sprache (aber keinen Zugang zu Hoder B()) und bei zwei Anordnungen von Box - IDs , welche die 16-Bit-Darstellungen von zwei ganzen Zahlen aund bIhre Aufgabe ist es , Produkte Box - IDs für die 16-Bit - Binärdarstellung von a+b(Überlauf verwerfen) mit der Mindestanzahl von F()Anrufen.

Die Lösung, die F()am wenigsten anruft, gewinnt. Krawatten werden durch Zählen der Gesamtzahl der x[],y[]Paare, F()mit denen aufgerufen wurde , unterbrochen - weniger ist besser. Wenn immer noch gebunden, bestimmt die Größe Ihres Codes (mit Ausnahme der Implementierung von F()und seiner Helfer) den Gewinner auf herkömmliche Weise. Bitte verwenden Sie einen Titel wie "MyLang, 123 Anrufe, 456 Paare, 789 Bytes" für Ihre Antwort.

Schreiben Sie eine Funktion oder ein komplettes Programm. Eingabe / Ausgabe / Argumente / Ergebnis sind int-Arrays in jedem vernünftigen Format. Die binäre Darstellung kann klein oder groß sein - wählen Sie eine aus.


Anhang 1: Um die Herausforderung etwas zu vereinfachen, können Sie davon ausgehen, dass Felder mit den IDs 0 und 1 die Werte 0 und 1 enthalten. Dies gibt Ihnen Konstanten, die beispielsweise für die Negation nützlich sind ( x^1ist "nicht"). Es gab natürlich Möglichkeiten, den Mangel an Konstanten zu umgehen, aber der Rest der Herausforderung ist sowieso schwer genug, also lasst uns diese Ablenkung beseitigen.


Anhang 2: Um das Kopfgeld zu gewinnen, müssen Sie einen der folgenden Schritte ausführen:

  • Veröffentlichen Sie Ihre Punktzahl (Anrufe, Paare, Bytes) und Ihren Code vor Ablauf der Frist

  • Veröffentlichen Sie Ihre Punktzahl und einen sha256-Hash Ihres Codes vor Ablauf der Frist. Geben Sie dann den tatsächlichen Code innerhalb von 23 Stunden nach Ablauf der Frist ein

ngn
quelle
Wenn ich dies in die Sprache meiner Wahl (Haskell) übersetzen würde, könnte ich die Wertrekursion verwenden und Fnur einmal aufrufen . Das wäre sicherlich Betrug, aber ich bin mir nicht sicher, ob es gut oder schlecht wäre.
Christian Sievers
Ich weiß, dass der globale Zustand in Haskell nicht willkommen ist, aber lassen Sie mich dies als Gedankenexperiment fragen: Wenn ich einen globalen Zähler bei der Implementierung von F erhöht hätte, um wie viel wäre er am Ende gewachsen? - das ist mein Verständnis von "Anzahl der Anrufe".
ngn
Ich könnte genau das tun, und es würde sagen 1. Aber es konnte nicht mit Ihrem Code zurück in JavaScript übersetzt werden. Im Wesentlichen würde ich sagen y=f(x)und davon xabhängen lassen y.
Christian Sievers
Ich fürchte, ich verstehe nicht, wie das funktionieren würde. Könnten Sie bitte Beispielcode zeigen? Mein Haskell ist arm, aber ich bin sicher, ich kann es herausfinden, ob ich mit dem Code spielen kann.
ngn
Vielleicht können wir die folgenden Typen verwenden, um dieses Problem zu modellieren? data Box = B Int deriving (Show); f :: [[[Box]]] -> [Box]Ich brauche mehr Zeit, um herauszufinden, wie man es implementiert f(Haskell erzwingt hier Kleinbuchstaben) - ich werde es morgen versuchen.
ngn

Antworten:

6

Python 3 , 5 Aufrufe, 92 Paare, 922 Bytes

Python 3 , 5 Aufrufe, 134 Paare, 3120 Bytes

Python 3 , 6 Aufrufe, 106 Paare, 2405 Bytes

[JavaScript (Node.js)], 9 Aufrufe, 91 Paare, 1405 Bytes

JavaScript (Node.js), 16 Aufrufe, 31 Paare, 378 Bytes

def add(F,a,b):r=[];p=lambda x:(x,x);q=lambda u,v,t:([u,v]+t[0],[u,v]+t[1]);s=lambda c,k,n:([e[j][n]for j in range(k,-1,-1)]+[f[n]],[c]+f[n-k:n+1]);t=lambda c,k,n:q(a[n],b[n],s(c,k,n-1));z=F([p([a[i],b[i]])for i in range(16)]+[([a[i]],[b[i]])for i in range(16)]);e=[z[0:16]];f=z[16:32];r+=[e[0][0]];c=f[0];z=F([p([a[1],b[1],c]),([e[0][1],f[1]],[c,f[1]])]+[([e[0][i]],[e[0][i-1]])for i in range(3,16)]);r+=[z[0]];c=z[1];e+=[[0]*3+z[2:15]];z=F([p([a[2],b[2],c]),t(c,0,3),s(c,1,3)]+[([e[j][i]],[e[1][i-j-1]])for j in range(2)for i in range(6+j,16)]);r+=z[0:2];c=z[2];e+=u(2,4,z[3:]);z=F([p([a[4],b[4],c])]+[t(c,i,i+5)for i in range(0,3)]+[s(c,3,7)]+[([e[j][i]],[e[3][i-j-1]])for j in range(4)for i in range(12+j,16)]);r+=z[0:4];c=z[4];e+=u(4,8,z[5:]);z=F([p([a[8],b[8],c])]+[t(c,i,i+9) for i in range(0,7)]);return r+z
def u(b,e,z):
	j=0;w=[0]*(e-b)
	for i in range(b,e):w[i-b]=[0]*(i+e)+z[j:j+16-(i+e)];j+=16-(i+e)
	return w

Probieren Sie es online aus!

ERSTE VERSION Okay, das ist kein Golf. Es ist nur eine Anpassung von @ ngns Code.

Die einzige Idee hier ist, dass Sie den letzten Übertrag nicht berechnen müssen, da Sie den Überlauf verwerfen. Außerdem werden die Anrufe Fvon zu zwei gruppiert. Vielleicht können sie auf andere Weise gruppiert werden, aber ich bezweifle, dass Sie die Anzahl der Paare aufgrund der Art des grundlegenden Additionsalgorithmus erheblich reduzieren können.

EDIT : Immer noch nicht Golf gespielt. Die Anzahl der Paare könnte sicherlich reduziert werden, und wahrscheinlich auch die Anzahl der Anrufe. Unter https://gist.github.com/jferard/864f4be6e4b63979da176bff380e6c62 finden Sie einen "Beweis" mit Sympy.

EDIT 2 Zu Python gewechselt, weil es für mich besser lesbar ist. Jetzt habe ich die allgemeine Formel, ich denke, ich kann das Limit von 5 (vielleicht 4) Anrufen erreichen.

EDIT 3 Hier sind die Grundbausteine:

alpha[i] = a[i] ^ b[i]
beta[i] = a[i] * b[i]
c[0] = beta[0]
r[0] = alpha[0]

Die allgemeine Formel lautet:

c[i] = alpha[i]*c[i-1] ^ beta[i]
r[i] = a[i] ^ b[i] ^ c[i-1]

Die erweiterte Version lautet:

c[0] = beta[0]
c[1] = alpha[1]*beta[0] ^ beta[1]
c[2] = alpha[2]*alpha[1]*beta[0] ^ alpha[2]*beta[1] ^ beta[2]
c[3] = alpha[3]*alpha[2]*alpha[1]*beta[0] ^ alpha[3]*alpha[2]*beta[1] ^ alpha[3]*beta[2] ^ beta[3]
...
c[i] = alpha[i]*...*alpha[1]*beta[0] ^ alpha[i]*...*alpha[2]*beta[1] ^ .... ^ alpha[i]*beta[i-1] ^ beta[i]

5 Anrufe scheinen mir das Limit zu sein. Jetzt habe ich ein wenig Arbeit, um Paare zu entfernen und Golf zu spielen!

EDIT 4 Ich habe diesen Golf gespielt.

Ungolfed Version:

def add(F, a, b):
    r=[]
    # p is a convenient way to express x1^x2^...x^n
    p = lambda x:(x,x)
    # q is a convenient way to express a[i]^b[i]^carry[i-1]
    q = lambda u,v,t:([u,v]+t[0],[u,v]+t[1])

    # step1: the basic bricks
    z=F([p([a[i],b[i]]) for i in range(16)]+[([a[i]],[b[i]]) for i in range(16)])
    alpha=z[0:16];beta=z[16:32]
    r.append(alpha[0])
    c = beta[0]

    # step 2
    z=F([
        p([a[1],b[1],c]),
        ([alpha[1],beta[1]],[c,beta[1]])
        ]+[([alpha[i]],[alpha[i-1]]) for i in range(3,16)])
    r.append(z[0])
    c = z[1] # c[1]
    alpha2=[0]*3+z[2:15]
    assert len(z)==15, len(z)

    # step 3
    t0=([alpha[2],beta[2]],[c,beta[2]])
    t1=([alpha2[3],alpha[3],beta[3]],[c,beta[2],beta[3]])
    z=F([
        p([a[2],b[2],c]),
        q(a[3],b[3],t0),
        t1]+
        [([alpha[i]],[alpha2[i-1]]) for i in range(6,16)]+
        [([alpha2[i]],[alpha2[i-2]]) for i in range(7,16)])
    r.extend(z[0:2])
    c = z[2] # c[3]
    alpha3=[0]*6+z[3:13]
    alpha4=[0]*7+z[13:22]
    assert len(z)==22, len(z)

    # step 4
    t0=([alpha[4],beta[4]],[c,beta[4]])
    t1=([alpha2[5],alpha[5],beta[5]],[c,beta[4],beta[5]])
    t2=([alpha3[6],alpha2[6],alpha[6],beta[6]],[c,beta[4],beta[5],beta[6]])
    t3=([alpha4[7],alpha3[7],alpha2[7],alpha[7],beta[7]],[c,beta[4],beta[5],beta[6],beta[7]])
    z=F([
        p([a[4],b[4],c]),
        q(a[5],b[5],t0),
        q(a[6],b[6],t1),
        q(a[7],b[7],t2),
        t3]+
        [([alpha[i]],[alpha4[i-1]]) for i in range(12,16)]+
        [([alpha2[i]],[alpha4[i-2]]) for i in range(13,16)]+
        [([alpha3[i]],[alpha4[i-3]]) for i in range(14,16)]+
        [([alpha4[i]],[alpha4[i-4]]) for i in range(15,16)])
    r.extend(z[0:4])
    c = z[4] # c[7]
    alpha5 = [0]*12+z[5:9]
    alpha6 = [0]*13+z[9:12]
    alpha7 = [0]*14+z[12:14]
    alpha8 = [0]*15+z[14:15]
    assert len(z) == 15, len(z)

    # step 5
    t0=([alpha[8],beta[8]],[c,beta[8]])
    t1=([alpha2[9],alpha[9],beta[9]],[c,beta[8],beta[9]])
    t2=([alpha3[10],alpha2[10],alpha[10],beta[10]],[c,beta[8],beta[9],beta[10]])
    t3=([alpha4[11],alpha3[11],alpha2[11],alpha[11],beta[11]],[c,beta[8],beta[9],beta[10],beta[11]])
    t4=([alpha5[12],alpha4[12],alpha3[12],alpha2[12],alpha[12],beta[12]],[c,beta[8],beta[9],beta[10],beta[11],beta[12]])
    t5=([alpha6[13],alpha5[13],alpha4[13],alpha3[13],alpha2[13],alpha[13],beta[13]],[c,beta[8],beta[9],beta[10],beta[11],beta[12],beta[13]])
    t6=([alpha7[14],alpha6[14],alpha5[14],alpha4[14],alpha3[14],alpha2[14],alpha[14],beta[14]],[c,beta[8],beta[9],beta[10],beta[11],beta[12],beta[13],beta[14]])
    t7=([alpha8[15],alpha7[15],alpha6[15],alpha5[15],alpha4[15],alpha3[15],alpha2[15],alpha[15],beta[15]],[c,beta[8],beta[9],beta[10],beta[11],beta[12],beta[13],beta[14],beta[15]])

    z=F([
        p([a[8],b[8],c]),
        q(a[9],b[9],t0),
        q(a[10],b[10],t1),
        q(a[11],b[11],t2),
        q(a[12],b[12],t3),
        q(a[13],b[13],t4),
        q(a[14],b[14],t5),
        q(a[15],b[15],t6)
    ])
    r.extend(z)
    return r

Probieren Sie es online aus!

jferard
quelle
Sehr gut :) Sie haben die zwei einfachen Optimierungen gefunden, die ich absichtlich ausgelassen habe. "Ich bezweifle, dass Sie die Anzahl der Paare erheblich reduzieren können" - beachten Sie, dass das erste Kriterium für den Gewinn die Anzahl der Anrufe bei ist F(). Ich garantiere, dass es eine Möglichkeit gibt, diese erheblich zu reduzieren (das ist der schwierigste Teil dieser Herausforderung), und dann wird es Raum geben, die Anzahl der Paare zu optimieren und schließlich natürlich den Code zu spielen (aber das ist das am wenigsten wichtige Kriterium).
ngn
OK ich habe es! Früher oder später hast du so etwas : ... + x * y * z + .... Wir können es nicht verwenden F, um es auszuwerten, aber wenn wir x * ymit dem vorherigen FAufruf berechnet haben, müssen wir nur Folgendes tun: ... + (x * y) * z + ...(es entspricht dem Format von F). Als ich mit Sympy spielte, konnte ich einen Anruf ersparen (Schritt 1: Berechne r0, c0, r1; Schritt 2: Berechne c1 und einige Hilfswerte; Schritt 3: Berechne r2, c2, r3, c3) und suche jetzt nach einem General Lösung.
Jferard
Ja, mit anderen Worten: Die Ausgangsbits sind Polynome mit einem Grad höher als 2 in den Eingangsbits. Das innere Produkt kann höchstens ein Polynom mit m und n Grad zu einem Polynom mit (m + n) Grad kombinieren.
Beeilen
Möglicherweise möchten Sie Anhang 2 oben nutzen. Oder: Wenn jemand Ihren Code kopiert, ein Leerzeichen entfernt und ihn erneut veröffentlicht, muss ich ihm technisch den Bonus gewähren.
ngn
2
Für die Aufzeichnung ist es unmöglich, weniger als fünf Aufrufe zu verwenden, da die Lösung ein Polynom vom Grad 32 erfordert. (Das Polynom, das einer Funktion der Eingangsbits entspricht, ist eindeutig.)
Nitrodon
2

Haskell, 1 Aufruf (Betrug ???), 32 Paare (könnte verbessert werden), 283 Bytes (gleich)

Bitte sei mir nicht böse, ich möchte damit nicht gewinnen, aber ich wurde in den Bemerkungen zur Herausforderung ermutigt, zu erklären, wovon ich sprach.

Ich habe versucht, mit der Statusmonade Boxen hinzuzufügen und Anrufe und Paare zu zählen, und das hat funktioniert, aber ich habe es nicht geschafft, meine Lösung in dieser Einstellung zum Laufen zu bringen. Also habe ich getan, was auch in den Kommentaren vorgeschlagen wurde: Verstecke einfach die Daten hinter einem Datenkonstruktor und gucke nicht. (Der saubere Weg wäre, ein separates Modul zu verwenden und den Konstruktor nicht zu exportieren.) Diese Version hat den Vorteil, dass sie viel einfacher ist.

Da es sich um Bitboxen handelt, habe ich BoolWerte in sie eingefügt. Ich definiere zeroals die angegebene Box mit dem Nullbit - a onewird nicht benötigt.

import Debug.Trace

data B = B { unB :: Bool }

zero :: B
zero = B False

f :: [([B],[B])] -> [B]
f pairs =  trace ("f was called with " ++ show (length pairs) ++ " pairs") $
           let (B i) &&& (B j) = i && j
           in map (\(x,y) ->  B ( foldl1 (/=) (zipWith (&&&) x y))) pairs

Wir verwenden die Debugging-Funktion trace zu sehen, wie oft fund mit wie vielen Paaren aufgerufen wurde. &&&schaut in die Kästchen durch Mustervergleich, die /= für BoolWerte verwendete Ungleichung ist xor.

bits :: Int -> [Bool]
bits n = bitsh n 16
  where bitsh _ 0 = []
        bitsh n k = odd n : bitsh (n `div` 2) (k-1)

test :: ( [B] -> [B] -> [B] ) -> Int -> Int -> Bool
test bba n m = let x = map B (bits n)
                   y = map B (bits m)
                   r = bba x y
                   res = map unB r
               in res==bits(n+m)

Die testFunktion verwendet einen blinden binären Addierer als erstes Argument und dann zwei Zahlen, für die die Addition getestet wird. Es wird angezeigt Bool, ob der Test erfolgreich war. Zuerst werden die Eingabefelder erstellt, dann wird der Addierer aufgerufen, das Ergebnis entpackt (mit unB) und mit dem erwarteten Ergebnis verglichen.

Ich habe zwei Addierer implementiert, die Beispiellösung simple, damit wir sehen können, dass die Debug-Ausgabe korrekt funktioniert, und meine Lösung mithilfe der Wertrekursion valrec.

simple a b = let [r0] = f [([a!!0,b!!0],[a!!0,b!!0])]
                 [c]  = f [([a!!0],[b!!0])]
             in loop 1 [r0] c
             where loop 16 rs _ = rs
                   loop i  rs c = let [ri] = f [([a!!i,b!!i,c],[a!!i,b!!i,c])]
                                      [c'] = f [([a!!i,b!!i,c],[b!!i,c,a!!i])]
                                  in loop (i+1) (rs++[ri]) c'

valrec a b =
    let res = f (pairs res a b)
    in [ res!!i | i<-[0,2..30] ]
  where pairs res a b =
           let ts = zipWith3 (\x y z -> [x,y,z])
                             a b (zero : [ res!!i | i<-[1,3..29] ]) in
           [ p | t@(h:r) <- ts, p <- [ (t,t), (t,r++[h]) ] ]

Sehen Sie, wie ich resin Bezug auf sich selbst definiere? Das wird auch als Knotenbinden bezeichnet .

Jetzt können wir sehen wie f nur einmal aufgerufen wird:

*Main> test valrec 123 456
f was called with 32 pairs
True

Oder ersetzen valrec durch simple, zu sehen, fdass 32 Mal aufgerufen wird.

Probieren Sie es online aus! (Die Tracing-Ausgabe erscheint unter "Debug")

Christian Sievers
quelle
Keine Wut hier :) Wenn ich das richtig verstehe, ist das Argument feine faule, möglicherweise unendliche Liste, die sich materialisiert, wenn Sie sie durchlaufen? Ich fürchte , das ist , gegen den Geist der Herausforderung - es lässt Sie die Entscheidung über verschieben , was als das passieren i+1-st Argument bis nach Sie das Ergebnis erhalten haben an den entsprechenden i-te. Es ist viel interessanter herauszufinden, wie viele Anrufe fSie mit vollständig materialisierten, unveränderlichen Argumenten benötigen :)
ngn
Genau. @jferard hat erstaunliche Arbeit geleistet, die durch einen solchen Trick nicht entkräftet werden sollte. Es fkönnte zwar unendlich viel Eingabe geben (unendliche Bitströme hinzufügen, yay!), Aber das ist nicht der Punkt. Oh, und tatsächlich stellt die traceNachricht sicher, dass die Länge endlich und am Anfang bekannt ist. Ich würde auch nicht sagen, dass es eine aufgeschobene Entscheidung gibt: Alles wurde im Voraus geplant, wie gefordert, ich mische nur blind Kisten. Und beachten Sie, dass es nicht um die Reihenfolge der Argumente geht: Ich könnte es so ändern, dass es reszuerst das Ergebnis und dann die Übertragsbits enthält.
Christian Sievers
"Ich mische nur blind Kisten" - Angenommen, Sie haben eine Kiste erhalten, indem Sie angerufen haben f. Geben Sie dieses Feld als weiteres Argument im selben Aufruf an zurück f?
ngn
Ja, ich will. Darum geht es bei der Wertrekursion. Sie hatten das Recht: Es verwendet Faulheit und die Tatsache, dass ich Argumente verwenden kann, die nicht vollständig materialisiert sind (ich mag diese Beschreibung). Angesichts des offensichtlichen Geistes der Herausforderung ist das - wie angekündigt - eindeutig Betrug. Wenn man es für erfinderisch oder bemerkenswert hält, kann man argumentieren, dass es gut ist zu betrügen.
Christian Sievers
Es ist sicherlich von der guten Art - offensichtlich haben Sie nicht die Absicht, hier zu täuschen. Faulheit in der funktionalen Programmierung ist ein schönes Konzept und hat seine gültigen Verwendungen. Als ich vor einigen Jahren versuchte, etwas über Haskell zu lernen, war ich sehr beeindruckt von einem Einzeiler, der den Knoten für die Fibonacci-Zahlen knüpft.
ngn
0

JavaScript, 32 Aufrufe, 32 Paare, 388 Bytes

Dyalog APL, 32 Aufrufe, 32 Paare, 270 Bytes

Dies ist eine naive Beispiellösung, die als Vorlage dienen kann.

Beachten Sie, dass die Byteanzahl nur den Abschnitt enthalten darf, der von "BEGIN / END SOLUTION" umgeben ist.

Erläuterung:

Ich habe die Little-Endian-Bitreihenfolge gewählt ( x[0]ist das niedrigstwertige Bit).

Beachten Sie, dass Einzelbit-Additionsmod 2 als F([[[x,y],[x,y]]])(dh: x*x ^ y*y- Multiplikationsmod 2 ist idempotent) und binäre Multiplikation als realisiert werden kannF([[[x],[y]]]) .

Wir durchlaufen die Bits von niedrigstwertig zu höchstwertig und berechnen bei jedem Schritt ein Ergebnisbit und einen Übertrag.

#!/usr/bin/env node
'use strict'
let H=[0,1]
,B=x=>H.push(x)-1
,nCalls=0
,nPairs=0
,F=pairs=>{
  nCalls++;nPairs+=pairs.length
  return pairs.map(([x,y])=>{let s=0;for(let i=0;i<x.length;i++)s^=H[x[i]]*H[y[i]];return B(s)})
}

// -----BEGIN SOLUTION-----
var f=(a,b)=>{
  var r=[], c // r:result bits (as box ids), c:carry (as a box id)
  r[0]=F([[[a[0],b[0]],[a[0],b[0]]]])          // r0 = a0 ^ b0
  c=F([[[a[0]],[b[0]]]])                       // c = a0*b0
  for(var i=1;i<16;i++){
    r.push(F([[[a[i],b[i],c],[a[i],b[i],c]]])) // ri = ai ^ bi ^ c
    c=F([[[a[i],b[i],c],[b[i],c,a[i]]]])       // c = ai*bi ^ bi*c ^ c*ai
  }
  return r
}
// -----END SOLUTION-----

// tests
let bits=x=>{let r=[];for(let i=0;i<16;i++){r.push(x&1);x>>=1}return r}
,test=(a,b)=>{
  console.info(bits(a))
  console.info(bits(b))
  nCalls=nPairs=0
  let r=f(bits(a).map(B),bits(b).map(B))
  console.info(r.map(x=>H[x]))
  console.info('calls:'+nCalls+',pairs:'+nPairs)
  console.assert(bits(a+b).every((x,i)=>x===H[r[i]]))
}

test(12345,6789)
test(12,3)
test(35342,36789)

Das gleiche gilt für Dyalog APL (jedoch unter Verwendung randomisierter Box-IDs):

⎕io←0⋄K←(V←⍳2),2+?⍨1e6⋄B←{(V,←⍵)⊢K[≢V]}⋄S←0⋄F←{S+←1,≢⍵⋄B¨2|+/×/V[K⍳↑⍉∘↑¨⍵]}
⍝ -----BEGIN SOLUTION-----
f←{
  r←F,⊂2⍴⊂⊃¨⍺⍵        ⍝ r0 = a0 ^ b0
  c←⊃F,⊂,¨⊃¨⍺⍵        ⍝ c = a0*b0
  r,⊃{
    ri←⊃F,⊂2⍴⊂⍺⍵c     ⍝ ri = ai ^ bi ^ c
    c⊢←⊃F,⊂(⍺⍵c)(⍵c⍺) ⍝ c = ai*bi ^ bi*c ^ c*ai
    ri
  }¨/1↓¨⍺⍵
}
⍝ -----END SOLUTION-----
bits←{⌽(16⍴2)⊤⍵}
test←{S⊢←0⋄r←⊃f/B¨¨bits¨⍺⍵
      ⎕←(↑bits¨⍺⍵)⍪V[K⍳r]⋄⎕←'calls:' 'pairs:',¨S
      (bits⍺+⍵)≢V[K⍳r]:⎕←'wrong!'}
test/¨(12345 6789)(12 3)(35342 36789)
ngn
quelle