Bounce-Modulo zwei Zahlen

12

Das Diagramm der Modulo-Operation ( ) sieht folgendermaßen aus:y=xmodk

Graph der Modulofunktion

Dies ist eine sehr nützliche Funktion, da wir so ein "Wrapping" -Verhalten erzeugen können. Es ist jedoch sehr umständlich, wenn ich es verwenden möchte, um eine Erscheinung des "Springens" zwischen zwei Wänden zu erzeugen. Der Graph der "Bounce" -Funktion ( ) sieht folgendermaßen aus:y=bounce(x,k)

Graph der "Bounce-Modulo" -Funktion

Die Periode des Graphen vony=xmodk ist . Die Periode des Graphen von ist , weil es sich für Einheiten nach oben und dann für andere Einheiten nach unten bewegt , bevor es zu seinem Ausgangspunkt zurückkehrt. Für beide Funktionen ist der Minimalwert für 0 und der Maximalwert ist (tatsächlich ist er für die Modulfunktion mit integralen Eingängen ). Außerdem ist für beide Funktionen der Wert, bei dem ist, 0.ky=bounce(x,k)2kkkykk1x=0

Die Herausforderung

Geben Sie bei einer Ganzzahl und einer positiven Ganzzahl eine Ganzzahl- oder Gleitkommanäherung von .xky=bounce(x,k)

Dies ist , also gewinnt die kürzeste gültige Übermittlung (in Bytes gezählt).

Testfälle

  x,  k -> bounce(x, k)
  0, 14 ->            0
  3,  7 ->            3
 14, 14 ->           14
 15, 14 ->           13
-13, 14 ->           13 (12.999997 etc would be an acceptable answer)
-14, 14 ->           14
191,  8 ->            1
192,  8 ->            0

Bonuspunkte für einen Fourier- basierten Ansatz in Fourier .

Esolanging Fruit
quelle
" Für beide Funktionen ist der Minimalwert für x 0 und der Maximalwert ist k " ist einfach falsch.
Peter Taylor
@ PeterTaylor Hoppla. Ich meine das Ergebnis.
Esolanging Fruit
1
Hoppla, das habe ich schon gesagt. Es ist immer noch falsch. k % k = 0
Peter Taylor
@ PeterTaylor Oh, ich verstehe deine Frage. Ich hatte dies ursprünglich mit dem Gedanken an Gleitkommazahlen entworfen und danach auf nur wenige Zentimeter umgestellt. Wird bearbeiten.
Esolanging Fruit
1
@PeterTaylor Wenn es sich bei den Argumenten um Gleitkommazahlen handelt, ist das Maximum eine Zahl, die beliebig nahe kommt k.
Esolanging Fruit

Antworten:

7

x86-64-Maschinencode, 18 Byte

97
99
31 D0
29 D0
99
F7 FE
29 D6
A8 01
0F 45 D6
92
C3 

Dieser Code definiert eine Funktion in der x86-64-Maschinensprache (die berechnet bounce(x, k). Gemäß der auf Gnu / Unix-Systemen verwendeten AMD64-Aufrufkonvention von System V wird der xParameter im übergebenEDI Register übergeben, während der kParameter im ESIRegister übergeben wird. Wie bei allen x86-Aufrufkonventionen wird das Ergebnis im EAXRegister zurückgegeben.

Um dies von C aus aufzurufen, würden Sie einen Prototyp wie folgt erstellen:

int Bounce(int x, int k);

Probieren Sie es online!

Ungolfed Assembler-Mnemonik:

; Take absolute value of input 'x' (passed in EDI register).
; (Compensates for the fact that IDIV on x86 returns a remainder with the dividend's sign,
; whereas we want 'modulo' behavior---the result should be positive.)
xchg   eax, edi      ; swap EDI and EAX (put 'x' in EAX)
cdq                  ; sign-extend EAX to EDX:EAX, effectively putting sign bit in EDX
xor    eax, edx      ; EAX ^= EDX
sub    eax, edx      ; EAX -= EDX

; Divide EDX:EAX by 'k' (passed in ESI register).
; The quotient will be in EAX, and the remainder will be in EDX.
; (We know that EAX is positive here, so we'd normally just zero EDX before division,
; but XOR is 2 bytes whereas CDQ is 1 byte, so it wins out.)
cdq
idiv   esi

; Pre-emptively subtract the remainder (EDX) from 'k' (ESI),
; leaving result in ESI. We'll either use this below, or ignore it.
sub    esi, edx

; Test the LSB of the quotient to see if it is an even number (i.e., divisible by 2).
; If not (quotient is odd), then we want to use ESI, so put it in EDX.
; Otherwise (quotient is even), leave EDX alone.
test   al, 1
cmovnz edx, esi

; Finally, swap EDX and EAX to get the return value in EAX.
xchg   eax, edx
ret

Beachten Sie, dass der erste Abschnitt (der den absoluten Wert annimmt) äquivalent geschrieben worden sein könnte:

; Alternative implementation of absolute value
xchg    eax, edi
neg     eax
cmovl   eax, edi

Das ist genau die gleiche Anzahl von Bytes (6). Die Leistung sollte ähnlich sein, vielleicht etwas schneller (außer am bestimmten Intel-Chips, bei denen bedingte Bewegungen langsam sind ).

XCHGist natürlich relativ langsam und wäre nicht vorzuziehen, MOVaußer beim Code-Golfen (das erstere ist 1 Byte, wenn einer der Operanden der Akkumulator ist, wohingegen ein Register-Register MOVimmer 2 Byte ist).

Cody Gray
quelle
6

Gelee , 3 Bytes

æ%A

Probieren Sie es online!

Eingebaute ftw.

Erläuterung

æ%ist ein nützliches eingebautes hier. Ich weiß nicht, wie ich es beschreiben soll, daher werde ich nur die Ausgabe für einige Eingaben bereitstellen:

Wie xgeht von 0unendlich, xæ%4geht, 0,1,2,3,4,(-3,-2,-1,0,1,2,3,4,)wo der Teil in Klammern bis unendlich in beide Richtungen wiederholt wird.

Undichte Nonne
quelle
3

Ruby, 40 Bytes 32 Bytes

b=->(x,k){(x/k+1)%2>0?x%k:k-x%k}

Probieren Sie es online!

Erläuterung

Hallo, das ist meine erste Antwort auf dieser Seite! Dieser Code basiert auf der Beobachtung, dass sich die Bounce-Funktion genau wie Modulo verhält, wenn ( n -1) k <= x < nk und n ungerade sind, und sich wie eine umgekehrte Modulo-Operation verhält, wenn n gerade ist. (x/k+1)ist die kleinste ganze Zahl größer als x / k (was x / k + 1 ist, abgerundet auf eine ganze Zahl). Daher (x/k+1)findet sich das oben erwähnte n . %2>0prüft, ob n ungerade oder gerade ist. Wenn n mod 2> 0 ist, dann ist n ungerade. Wenn nmod 2 = 0, dann ist n gerade. Wenn n ungerade ist, sollte die Sprungfunktion gleich x mod k sein . Wenn n gerade ist, sollte die Sprungfunktion umgekehrt sein, gleich k - x mod k . Der gesamte Ausdruck (x/k+1)%2>0?x%k:k-x%kfindet n und führt dann das x mod k aus, wenn es ungerade ist, und führt sonst k - x mod k aus .

Die Antwort wurde auf Vorschlag von Cyoce verbessert .

CyborgOctopus
quelle
Sie können dies in ein Lambda umwandeln. Anstelle der def b(x,k) ... endVerwendung->x,k{...}
Cyoce
Und da Sie es mit ganzen Zahlen zu tun haben, .to_iist dies nicht erforderlich.
Cyoce
2

Mathematica, 19 Bytes

Abs@Mod[#,2#2,-#2]&
Alephalpha
quelle
1

J, 25 Bytes

Hinweis:

Dies ist nur ein reguläres Modulo auf den Leiternummern. Zum Beispiel im Fall von 5:0 1 2 3 4 5 4 3 2 1

Hier ist eine (noch nicht gut eingespielte) Lösung in J. Wir werden versuchen, uns morgen zu verbessern:

[ ((|~ #) { ]) (i.@>:,}:@i.@-) @ ]

komprimiert: [((|~#){])(i.@>:,}:@i.@-)@]

komprimiert2: [((|~#){])(<:|.|@}.@i:)@]

Probieren Sie es online!

Jona
quelle
Ich habe das Gefühl i:, hier verwendet werden zu können, aber ich habe noch keine Lösung ausprobiert
Conor O'Brien
@ ConorO'Brien check meine compress2 Version aus, es spart ein paar Bytes mit i:. Habe gerade keine Zeit gehabt, die Hauptversion zu aktualisieren und eine Erklärung abzugeben. Ich gehe davon aus, dass ein Experte mindestens 4 oder 5 weitere Bytes abschneiden könnte ...
Jonah,
((|~#){])]-|@}:@i:für 18 Bytes
Meilen
@ Meilen schön, Tyvm
Jonah
1

QBIC , 25 30 27 Bytes

g=abs(:%:)~a'\`b%2|?b-g\?g

Hab ein bisschen umstrukturiert ...

Erläuterung

g=abs(   )  let g be the absolute value of 
       %    the (regular) modulo between
      : :   input a read from cmd line, and input b read from cmd line
~a \ b%2    IF the int division of A and B mod 2 (ie parity test) yields ODD
  ' `         (int divisions need to be passed to QBasic as code literals, or ELSE...)
|?b-g       THEN print bouncy mod
\?g         ELSE print regular mod
steenbergh
quelle
Macht QBIC etwas anderes für MOD-Operationen als andere Basic-Implementierungen? Andere Basics geben MOD mit dem gleichen Vorzeichen wie die Dividende zurück. das würde scheitern, wenn xist -13 und kist 14.
Cody Gray
@CodyGray Nein, es gab -13. Jetzt behoben.
Steenbergh
Brauchst du nicht absbeide Male?
Neil
@Neil hast du einen Testfall dafür?
Steenbergh
@Neil nvm, ich habe es durch Umstrukturierung der ganzen Sache behoben.
Steenbergh
1

C89, 40 Bytes

t;f(x,k){t=abs(x%k);return x/k%2?k-t:t;}

AC-Port meiner x86-Maschinencode-Antwort , dies definiert eine Funktion f, die das Bounce-Modulo für die Parameter xund berechnet k.

Es wird die implicit-int-Regel von C89 verwendet, sodass beide Parameter, die globale Variable tund der Rückgabewert der Funktion implizit vom Typ sind int. Die globale Variablet wird nur verwendet, um einen temporären Wert zu speichern, der letztendlich Bytes spart, verglichen mit dem Wiederholen der Berechnung auf beiden Seiten des bedingten Operators.

Die absFunktion (absoluter Wert) wird in der <stdlib.h>Kopfzeile bereitgestellt , muss jedoch hier nicht angegeben werden. Dies ist wiederum der impliziten Ganzzahl von C89 zu verdanken (in der die Funktion implizit deklariert und als zurückgegeben angenommen wird)int ) nicht hier aufgenommen werden.

Probieren Sie es online!

Ungolfed-Version:

#include <stdlib.h>

int Bounce(int x, int k)
{
    int mod = abs(x % k);
    return (x/k % 2) ? k-mod : mod;
}

In Anbetracht meines handoptimierten Maschinencodes generieren Compiler tatsächlich eine ziemlich gute Ausgabe dafür. Ich meine, sie sollten; Es ist eine ziemlich einfache Funktion zum Optimieren! Ich habe jedoch einen kleinen Fehler im x86-64-Optimierer von GCC entdeckt , bei dem merkwürdigerweise größerer Code erzeugt wird , wenn Sie ihn zur Optimierung der Größe auffordern, und kleinerer Code, wenn Sie ihn zur Optimierung der Geschwindigkeit auffordern .

Cody Gray
quelle
m;f(x,k){m=abs(x%k);x=x/k%2?k-m:m;}ist kürzer
Kritixi Lithos
Abgesehen davon, dass es nicht wirklich einen Wert @cows zurückgibt, außer unter bestimmten, nicht definierten Umständen, da der GCC-Codegenerator auf x86-Zielen eine Besonderheit darstellt. Es ist eine Vorlage, die von den Leuten hier verwendet wird, aber für mich funktioniert es nicht mehr, als zufälligen Müll vom Stapel zu ziehen, was einfach die richtige Antwort ist.
Cody Grey
1

Haskell, 37 Bytes

Probieren Sie es online!

(!)=mod;x#k|odd$x`div`k=k-x!k|1<2=x!k

Verwendung:
Rufen Sie als 15#14für nicht negative linke Argumente und als (-13)#14für negative linke Argumente auf, da Haskell interpretieren würde, -13#14als -(13#14)ob Sie etwas wie verwenden ghci. Der TIO-Link akzeptiert einfach zwei Befehlszeilenargumente.

Erläuterung:
Definiert den binären Infixoperator zunächst so !, dass er mit dem Operator identisch ist mod. Haskells gibt modimmer einen nicht-negativen Wert aus, daher brauchen wir nicht die absLösungen, die andere hier haben. Dann wird geprüft, ob x/k(Ganzzahldivision) ungerade ist, und wenn ja, wird zurückgegeben k-x mod k(dh das Zurückspringen), oder es wird zurückgegeben x mod k.

SEJPM
quelle
Dies ist wahrscheinlich nur Geschmackssache, aber ich persönlich bevorzuge es nicht zu definieren, !da es keine Bytes mehr speichertx#k|odd$x`div`k=k-x`mod`k|1<2=x`mod`k
Mark S.
1

PHP, 40-50 Bytes

verdammte Dollar. Verdammter Importaufwand. :)

Ganzzahlige Version:

[,$x,$k]=$argv;$y=abs($x)%$k;echo$x/$k&1?$k-$y:$y;

oder

[,$x,$k]=$argv;echo[$y=abs($x)%$k,$k-$y][$x/$k&1];

float version, 56 bytes:

Ersetzen abs($x)%$kdurch fmod(abs($x),$k).


edit: fixe ergebnisse für negative x

Titus
quelle
4
"Verdammte Dollars". Ja, Geld stinkt ...
steenbergh
2
Wie wäre es mit €argvoder £argv? Die würden nett aussehen: x
Ismael Miguel
1

JavaScript (ES6), 36 32 Bytes

k=>f=x=>x<0?f(-x):x>k?k-f(k-x):x

Springt rekursiv xgegen 0und k, so sehr im Geiste der Herausforderung.

Neil
quelle
0

Common Lisp, 41 Bytes

(lambda(x k)(- k(abs(-(mod x(* k 2))k))))

Probieren Sie es online!

Renzo
quelle
0

C (GCC), 43 53 Bytes

Bearbeiten: Negatives Problem behoben

int f(int x,int y){return x/y%2?abs(y-x%y):abs(x%y);}

Probieren Sie es online!

Zachary Cotton
quelle
2
Dies liefert die falsche Antwort für (-13, 14) (-13 statt 13). Die Modul- und Restoperationen verhalten sich bei negativen Zahlen unterschiedlich.
CAD97,
0

R, 28 Bytes

pryr::f(abs((x-k)%%(2*k)-k))

Was zur Funktion auswertet:

function (k, x) 
abs((x - k)%%(2 * k) - k)

Welches scheint die Methode zu sein, die die meisten Lösungen verwenden. Ich habe sie nicht angesehen, bevor ich das gemacht habe.

JAD
quelle