C# Terme vereinfachen mit Ganzzahldivision und Modulo?

[Smagjus]

Zugegeben mehr Mathe als Informatik, trotzdem nicht das typische Matheproblem. Folgenden Code habe ich produziert:

​for (int i = 0; i < 81; i++)
 for (int j = 0; j < 9; j++)
  aLookup[i, j] = (i / 9 / 3 * 3 + i % 9 / 3) * 3 + ((i / 9 / 3 * 3 + i % 9 / 3) / 3) * 18 + j / 3 * 9 + j % 3;

Damit der Code etwas besser wartbar ist, wollte ich gucken, dass ich den Rechenterm etwas vereinfache. Ich kenne aber keine Regeln, die mir dies ermöglichen. Kann mir da jemand weiterhelfen? Oder gibt es hier garkeine Möglichkeit der Vereinfachung?

Das Array soll später so aussehen:

Spoiler: Array

 0     1     2     9    10    11    18    19    20    
 ​0     1     2     9    10    11    18    19    20    
 0     1     2     9    10    11    18    19    20    
 3     4     5    12    13    14    21    22    23    
 3     4     5    12    13    14    21    22    23    
 3     4     5    12    13    14    21    22    23    
 6     7     8    15    16    17    24    25    26    
 6     7     8    15    16    17    24    25    26    
 6     7     8    15    16    17    24    25    26    
 0     1     2     9    10    11    18    19    20    
 0     1     2     9    10    11    18    19    20    
 0     1     2     9    10    11    18    19    20    
 3     4     5    12    13    14    21    22    23    
 3     4     5    12    13    14    21    22    23    
 3     4     5    12    13    14    21    22    23    
 6     7     8    15    16    17    24    25    26    
 6     7     8    15    16    17    24    25    26    
 6     7     8    15    16    17    24    25    26    
 0     1     2     9    10    11    18    19    20    
 0     1     2     9    10    11    18    19    20    
 0     1     2     9    10    11    18    19    20    
 3     4     5    12    13    14    21    22    23    
 3     4     5    12    13    14    21    22    23    
 3     4     5    12    13    14    21    22    23    
 6     7     8    15    16    17    24    25    26    
 6     7     8    15    16    17    24    25    26    
 6     7     8    15    16    17    24    25    26    
27    28    29    36    37    38    45    46    47    
27    28    29    36    37    38    45    46    47    
27    28    29    36    37    38    45    46    47    
30    31    32    39    40    41    48    49    50    
30    31    32    39    40    41    48    49    50    
30    31    32    39    40    41    48    49    50    
33    34    35    42    43    44    51    52    53    
33    34    35    42    43    44    51    52    53    
33    34    35    42    43    44    51    52    53    
27    28    29    36    37    38    45    46    47    
27    28    29    36    37    38    45    46    47    
27    28    29    36    37    38    45    46    47    
30    31    32    39    40    41    48    49    50    
30    31    32    39    40    41    48    49    50    
30    31    32    39    40    41    48    49    50    
33    34    35    42    43    44    51    52    53    
33    34    35    42    43    44    51    52    53    
33    34    35    42    43    44    51    52    53    
27    28    29    36    37    38    45    46    47    
27    28    29    36    37    38    45    46    47    
27    28    29    36    37    38    45    46    47    
30    31    32    39    40    41    48    49    50    
30    31    32    39    40    41    48    49    50    
30    31    32    39    40    41    48    49    50    
33    34    35    42    43    44    51    52    53    
33    34    35    42    43    44    51    52    53    
33    34    35    42    43    44    51    52    53    
54    55    56    63    64    65    72    73    74    
54    55    56    63    64    65    72    73    74    
54    55    56    63    64    65    72    73    74    
57    58    59    66    67    68    75    76    77    
57    58    59    66    67    68    75    76    77    
57    58    59    66    67    68    75    76    77    
60    61    62    69    70    71    78    79    80    
60    61    62    69    70    71    78    79    80    
60    61    62    69    70    71    78    79    80    
54    55    56    63    64    65    72    73    74    
54    55    56    63    64    65    72    73    74    
54    55    56    63    64    65    72    73    74    
57    58    59    66    67    68    75    76    77    
57    58    59    66    67    68    75    76    77    
57    58    59    66    67    68    75    76    77    
60    61    62    69    70    71    78    79    80    
60    61    62    69    70    71    78    79    80    
60    61    62    69    70    71    78    79    80    
54    55    56    63    64    65    72    73    74    
54    55    56    63    64    65    72    73    74    
54    55    56    63    64    65    72    73    74    
57    58    59    66    67    68    75    76    77    
57    58    59    66    67    68    75    76    77    
57    58    59    66    67    68    75    76    77    
60    61    62    69    70    71    78    79    80    
60    61    62    69    70    71    78    79    80    
60    61    62    69    70    71    78    79    80

 

[Yuuri]

Du hast schon mal ne Klammer zu viel oder zu wenig drin.

 

[SymA]

Ich würd Werte die sich wiederholen grundsätzlich einer Variable zwischenspeichern, weil sich das auf Dauer positiv auf die Performance auswirkt selbst bei kleineren Operationen. Du musst bedenken, dass der Compiler jedes mal erneut viele verschiedene Prüfungen durchlaufen muss, auf Gültigkeit und Wert. Speicherst du in einer Variable zwischen entfallen diese Prüfungen bzw. fällt nur noch ein Bruchteil von Prüfungen an im Vergleich zur ständigen Neuberechnung der Werte.

 

[SoDaTierchen]

Naja, da kann ma naber auch selbst viel vereinfachen, auch ohne groß zu denken.

Wie viel ist denn i / 3 * 3? Korrekt: i. Und so kannst du das Array durchgehen und immer mit dem Gedanken, dass alle verwendeten Operatoren Linksassoziativ sind, überflüssige Operatoren einfach im Vorfeld ausrechnen.
HIER Findest du auch die Operator-Rangfolge, damit kannst du dir auch sicher sein, nichts falsch zu machen. Wobei bei dir alle Operatoren den selben Rang haben, außer des +. Das wird später ausgewertet.

​So, und nun viel Spaß beim Rechnen

 

[Smagjus]

Du hast schon mal ne Klammer zu viel oder zu wenig drin.

Ist korrigiert, das war ein Fehler beim kopieren

@48SymA
Ja, dafür ist das Array da. Das wird einmal bei der Initialisierung meines Programms gefüllt und kann dann während der Laufzeit abgefragt werden. Da sich aber noch etwas an der Logik des Programms ändern wird, wollte ich den Term davor vereinfachen.

 

[DocWindows]

(i / 81 + i % 9 / 3) * 3 + ((i / 81 + i % 3) / 3) * 18 + j / 27 + j % 3

Einfacher krieg ich es nicht hin

 

[Foochan]

Ich seh da ein Problem:

Seh ich das richtig, dass mit Integern gerechnet wird?
Falls ja, dann ist i / 9 / 3 * 3 nicht mehr das selbe wie i / 9.

Wenn man den genannten Term ersetzt, stimmt das Ausgabearray nicht mehr mit deinem gegebenen Array über ein, obwohl die Ersetzung mathematisch korrekt ist. (Vor allem die letzten Werte im Array stimmen nicht über ein)

Eine Lösung für das Problem hab ich leider nicht.

@DocWindows: i / 9 / 3 * 3 ist i / 9 und nicht i / 81 ;-)

 

[Freezedevil]

Man kann es auch in das allmächtige Wolfram Alpha einhacken und gucken was raus kommt.
Schau mal ob die eingegebene Formel dem entspricht was du rechnen möchtest http://www.wolframalpha.com/input/?...mod+9)+/+3)+/+3)+*+18+++j+/+3+*+9+++(j+mod+3)

i ist durch k ersetzt, da es sonst denkt i wäre die imaginäre Einheit.

 

[Smagjus]

Ich hatte das wohl nicht deutlich genug gemacht. Ja, es handelt sich natürlich um Integer. Ich guck mir mal die Formel bei Wolfram an.

Edit: Wolfram weiß natürlich nicht, dass es sich um Ganzzahldivision handelt, weshalb das leider nicht aufgeht. Außerdem hätte ich gerne das Handwerkszeug, um das in Zukunft dann selber machen zu können.

Edit2: Wolfram kann aber tatsächlich abrunden - ich guck mal, was damit rauskommt.

 

[Freezedevil]

Angeblich ist ein \ statt / Ganzzahldivision. http://www.wolframalpha.com/input/?...mod+9)+\+3)+\+3)+*+18+++j+\+3+*+9+++(j+mod+3)
Das Ergebnis ist aber das selbe. So wie ich das überblicke ist das auch immer ganzzahlig (wenn i und j ganzzahlig sind natürlich)

 

[Smagjus]

Hmm, komisch was Wolfram da ausspuckt.

Wenn ich die programmiersprache spezifische Devision in Wolfram "emuliere", dann kommt das dabei raus:
http://www.wolframalpha.com/input/?...+9+/+3))+/+3)+*+18+++floor(j+/+3)+*+9+++j+%+3
Ich würde sagen, es gibt einfach keine Möglichkeit, den Term zu vereinfachen.

Wenn ich das Ergebnis verwerte, was 34Freezedevil erhalten hat, dann erhalten ich für das Array übrigens folgende Belegung:

Spoiler: Freeze

  0      3      6      9    12    15    18    21    24      
  1      4      7    10    13    16    19    22    25    
  2      5      8    11    14    17    20    23    26    
  3      6      9    12    15    18    21    24    27    
  5      8    11    14    17    20    23    26    29    
  6      9    12    15    18    21    24    27    30    
  7    10    13    16    19    22    25    28    31    
  8    11    14    17    20    23    26    29    32    
10    13    16    19    22    25    28    31    34    
11    14    17    20    23    26    29    32    35    
12    15    18    21    24    27    30    33    36    
13    16    19    22    25    28    31    34    37    
15    18    21    24    27    30    33    36    39    
16    19    22    25    28    31    34    37    40    
17    20    23    26    29    32    35    38    41    
19    22    25    28    31    34    37    40    43    
20    23    26    29    32    35    38    41    44    
21    24    27    30    33    36    39    42    45    
22    25    28    31    34    37    40    43    46    
24    27    30    33    36    39    42    45    48    
25    28    31    34    37    40    43    46    49    
26    29    32    35    38    41    44    47    50    
27    30    33    36    39    42    45    48    51    
29    32    35    38    41    44    47    50    53    
30    33    36    39    42    45    48    51    54    
31    34    37    40    43    46    49    52    55    
33    36    39    42    45    48    51    54    57    
34    37    40    43    46    49    52    55    58    
35    38    41    44    47    50    53    56    59    
36    39    42    45    48    51    54    57    60    
38    41    44    47    50    53    56    59    62    
39    42    45    48    51    54    57    60    63    
40    43    46    49    52    55    58    61    64    
41    44    47    50    53    56    59    62    65    
43    46    49    52    55    58    61    64    67    
44    47    50    53    56    59    62    65    68    
45    48    51    54    57    60    63    66    69    
46    49    52    55    58    61    64    67    70    
48    51    54    57    60    63    66    69    72    
49    52    55    58    61    64    67    70    73    
50    53    56    59    62    65    68    71    74    
52    55    58    61    64    67    70    73    76    
53    56    59    62    65    68    71    74    77    
54    57    60    63    66    69    72    75    78    
55    58    61    64    67    70    73    76    79    
57    60    63    66    69    72    75    78    81    
58    61    64    67    70    73    76    79    82    
59    62    65    68    71    74    77    80    83    
60    63    66    69    72    75    78    81    84    
62    65    68    71    74    77    80    83    86    
63    66    69    72    75    78    81    84    87    
64    67    70    73    76    79    82    85    88    
66    69    72    75    78    81    84    87    90    
67    70    73    76    79    82    85    88    91    
68    71    74    77    80    83    86    89    92    
69    72    75    78    81    84    87    90    93    
71    74    77    80    83    86    89    92    95    
72    75    78    81    84    87    90    93    96    
73    76    79    82    85    88    91    94    97    
74    77    80    83    86    89    92    95    98    
76    79    82    85    88    91    94    97    100    
77    80    83    86    89    92    95    98    101    
78    81    84    87    90    93    96    99    102    
80    83    86    89    92    95    98    101    104    
81    84    87    90    93    96    99    102    105    
82    85    88    91    94    97    100    103    106    
83    86    89    92    95    98    101    104    107    
85    88    91    94    97    100    103    106    109    
86    89    92    95    98    101    104    107    110    
87    90    93    96    99    102    105    108    111    
88    91    94    97    100    103    106    109    112    
90    93    96    99    102    105    108    111    114    
91    94    97    100    103    106    109    112    115    
92    95    98    101    104    107    110    113    116    
93    96    99    102    105    108    111    114    117    
95    98    101    104    107    110    113    116    119    
96    99    102    105    108    111    114    117    120    
97    100    103    106    109    112    115    118    121    
99    102    105    108    111    114    117    120    123    
100    103    106    109    112    115    118    121    124    
101    104    107    110    113    116    119    122    125

 

[Grantig]

Das mit floor ist schon ein guter Ansatz.
Wenn Wolfram da nichts brauchbares ausspuckt, dann wirst du den Term auch nicht weiter vereinfachen können.

Was du evtl. machen kannst um den Code etwas übersichtlicher zu gestalten ist, einen Teil des Terms zu substituieren.
Also so:

int x = (i / 9 / 3 * 3 + i % 9 / 3);
aLookup[i, j] = x * 3 + (x / 3) * 18 + j / 3 * 9 + j % 3;

 

[Smagjus]

Ich werde dann wohl einfach substituieren. Danke an alle

 

[Freezedevil]

Dann muss eben etwas Gehirnschmalz helfen. Ich hab gerade mal ein bisschen getüftelt und die angenehmste Formel die ich bisher finden konnte ist:

i - i%27 + i%9 - i%3 + i%9/9*18 + j/3*9 + j%3

Ich habe das ganze in Python getestet, aber das sollte ja keine Rolle spielen. Wenn du den folgenden Code ausführst (zB HIER reincopieren und auf run) kannst du das erstellte Array nochmal begutachten, aber ich habe die beiden Felder in der letzten Zeile auch verglichen. Da der Vergleich true liefert sollten die schon gleich sein. ( // steht in Python für Ganzzahldivision)

from operator import eq
list1 = [[] for _ in range(81)]
for i in range(81):
    for j in range(9):
        list1[i].append((i//9//3*3 + i%9//3)*3 + ((i//9//3*3 + i%9//3)//3)*18 + j//3*9 + j%3)

list2 = [[] for _ in range(81)]
for i in range(81):
    for j in range(9):
        list2[i].append(i - i%27 + i%9 - i%3 + i%9//9*18 + j//3*9 + j%3)


for i in list2:
    print i


print all(map(eq, list1, list2))

Ergänzung (16. Oktober 2013)

Es wird doch langsam wenn man kurz darüber nachdenkt ist i%9/9 immer 0. daher folgende Vereinfachung

i - i%27 + i%9 - i%3 + j/3*9 + j%3

 

[Smagjus]

Ah, danke, damit hab ich nicht mehr gerechnet

ber ich glaube ich habe jetzt den Dreh raus. Ich gucke, ob sich damit noch mehr machen lässt. Aber erstmal mach ich mal ein paar Laufzeit Überprüfungen.

Ergänzung (16. Oktober 2013)

Die Laufzeit verringert sich um mehr als die Hälfte mit den Verbesserungen. Natürlich ist das in dem Fall völlig unwichtig, aber ich stehe nunmal auf Zahlen

Auf 100.000 Durchläufe hochskaliert und mit simpelster Testmethodik:
​

#1      00:03.3601922
#2      00:01.5500886

 

[Freezedevil]

Das ist doch was!

 

[Smagjus]

Ich habe noch eine allerletzte Verbesserung gefunden, indem ich die Funktionswerte überprüft habe:
Statt:

i - i % 27 + i % 9 - i % 3 + j / 3 * 9 + j % 3;

Heißt es nun:

i - i % 27 + i % 9 - i % 3 + j / 3 * 6 + j;

Damit habe ich jetzt genug Zeit mit einer einzigen Programmzeile verbracht. Weiter geht's