1. Diese Seite verwendet Cookies. Wenn du dich weiterhin auf dieser Seite aufhältst, akzeptierst du unseren Einsatz von Cookies. Weitere Informationen

64bit integers auf 32bit system multiplizieren

Dieses Thema im Forum "Sonstige Sprachen" wurde erstellt von Cymatoxa, 22. Januar 2014.

  1. Cymatoxa

    Cymatoxa Mitglied

    Hallo zusammen,

    im Rahmen eines Uniprojekts entwickle ich ein Programm, das große Fiboneccizahlen berechnen soll.
    Dies soll allerdings in Assembler geschehen. Mein Problem ist aktuell, dass der verwendete Chip nur 32bit unterstützt.
    Interessanter Weise ist es möglich aus der Multiplikation zweier 32bit ints einen 64bit-Wert zu erhalten, ich möchte aber auch unit64 miteinander multiplizieren. (Wie) ist das möglich?
    Irgendwo habe ich gelesen, dass dies funktionieren sollte:
    Code (Text):
    1. // _L <-> lower bits [0...31]
    2. // _H <-> higher bits [32...63]
    3. result_L = a_L x b_L
    4. result_H = a_L x b_H + a_H x b_L
    Ich bin das mal durchgegangen, es schein nicht zu funktionieren.
    Es würde mich freuen, wenn ihr mir helfen könntet :)

    Schöne Grüße und gute Nacht,

    Cymatoxa
     
  2. sheel

    sheel I love Asm Administrator

    Und das ist welche Asm-Sprache bzw. Chip...?
     
  3. Cymatoxa

    Cymatoxa Mitglied

    Das ganze soll auf einem BeagleBoard xM mit ARM Cortex-A8 Prozessor laufen.
    Die Benutzereingabe (die Position der Fibonacci-Zahl) wird in C gelesen und auch die Ausgabe soll in C geschehen, lediglich die Berechnung soll in einer externen Methode
    Code (Text):
    1. extern unsigned long long _fibonacci(unsigned int n)
    geschehen. Ich bin mir ehrlich gesagt nicht sicher, welche Asm-Sprache das exakt sein soll, mir war nicht einmal bewusst, dass es da große Unterschiede gibt, es wird aber der ARM Standard-Befehlssatz unterstützt, außerdem gibt es eine NEON Einheit, die ich aber nicht brauchen sollte.

    Schöne Grüße,

    Cymatoxa
     
  4. Matthias Reitinger

    Matthias Reitinger ɐɯıǝɹ

    Hallo Cymatoxa,

    der Fehler bei deiner Berechnungsvorschrift ist, dass der Übertrag in der Berechnung von result_H nicht berücksichtigt wird. Richtig wäre:
    Code (Text):
    1. result_L = a_L × b_L
    2. result_H = a_L × b_H + a_H × b_L + (a_L × b_L) / 2^32
    Ich kenne mich nicht sonderlich gut mit dem ARM-Instruktionsset aus, aber mit drei Instruktionen kriegt man es meiner Meinung nach so hin:
    Code (Text):
    1. UMULL result_L, result_H, a_L, b_L  // result_L = a_L × b_L, result_H = (a_L × b_L) / 2^32
    2. MLA result_H, a_L, b_H, result_H    // result_H = result_H + a_L × b_H
    3. MLA result_H, a_H, b_L, result_H    // result_H = result_H + a_H × b_L
    Wobei man natürlich noch entsprechende Registernamen einsetzen muss.

    Jetzt müsstest du uns aber noch erklären, wozu man bei der Berechnung von Fibonacci-Zahlen eine Multiplikation benötigt.

    Grüße
    Matthias
     
    Zuletzt bearbeitet: 22. Januar 2014
  5. Cymatoxa

    Cymatoxa Mitglied

    Danke Matthias!

    Genau das habe ich gesucht.
    Die Aufgabenstellung erfordert es, dass die Fibonacci-Zahl an Stelle n mithilfe von Matrixexmultiplikation bestimmt wird. Die Formel dazu ist relativ simpel:
    c8f091b6d47f0da5bb50daec21fa56a9.png
    Alle Fib-Zahlen < 2^64 sollen damit berechnet werden können.

    Vielen Dank für deine Hilfe, gute Nacht und schöne Grüße

    Cymatoxa
     
  6. Matthias Reitinger

    Matthias Reitinger ɐɯıǝɹ

    Hallo Cymatoxa,

    danke für die Erklärung mit der Matrizendarstellung der Fibonacci-Zahlen. Das ist vor allem deswegen interessant, weil sich die Potenz mit binärer Exponentation berechnen lässt (ich schätze mal die Aufgabe zielt darauf ab) :)

    Grüße
    Matthias
     
  7. Cymatoxa

    Cymatoxa Mitglied

    Hi nochmal,

    genau das war der Plan ;) Ist zwar nicht direkt vorgegeben, aber es wurde mehrmals betont, dass ein großes Augenmerk auf Performanz liegt. Die Aufgabe ist im Grunde relativ simpel, ich hätte aber nie gedacht, dass mir eine einfache Multiplikation solche Probleme bereiten kann.
    Deine Lösung habe ich umgesetzt und es funktioiert einwandfrei.
    Sollte es jemanden interessieren:
    Code (Text):
    1. .globl _mult
    2. .code 32
    3.  
    4. ## uint64 _mult(uint64, uint64);
    5.  
    6. _mult:
    7.  
    8. ## parameter/return:
    9. ## var1 lo bits: r0
    10. ## var1 hi bits: r1
    11. ## var2 lo bits: r2
    12. ## var2 hi bits: r3
    13.  
    14. ## Since we are working with 64 bit integers
    15. ## we have to distingush between the lower
    16. ## bits [0...31] and the higher bits [32...63]
    17. ## the resulting Lo bits are stored in r0,
    18. ## the resulting Hi bits in r1.
    19. ## To calculate the product of both values
    20. ## we need some tmp vars (r4...r7) for the
    21. ## higher bits
    22.  
    23. ## make room for local temp vars
    24. push {r4, r5, r6, r7, lr}
    25.  
    26. ## r4  <-->  r_H = a_L × b_H + a_H × b_L + (a_L × b_L) / 2^32
    27. ## r0  <-->  r_L = a_L × b_L
    28. mul r4, r0, r3
    29. mul r5, r1, r2
    30. umull r0, r7, r0, r2
    31. add r4, r4, r5
    32. add r1, r4, r7
    33.  
    34. ## restore vars and jump back
    35. pop {r4, r5, r6, r7, pc}
    Schöne Grüße,

    Cymatoxa


    Edit: Sorry, hab mir angewöht, massig zu kommentieren ;D
     
Die Seite wird geladen...