64bit integers auf 32bit system multiplizieren

[Cymatoxa]

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:

// _L <-> lower bits [0...31]
// _H <-> higher bits [32...63]
result_L = a_L x b_L
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

 

[sheel]

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

 

[Cymatoxa]

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

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

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

 

[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:

result_L = a_L × b_L
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:

UMULL result_L, result_H, a_L, b_L  // result_L = a_L × b_L, result_H = (a_L × b_L) / 2^32
MLA result_H, a_L, b_H, result_H    // result_H = result_H + a_L × b_H
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

 

[Cymatoxa]

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:

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

 

[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

 

[Cymatoxa]

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:

.globl _mult
.code 32

## uint64 _mult(uint64, uint64);

_mult:

## parameter/return:
## var1 lo bits: r0
## var1 hi bits: r1
## var2 lo bits: r2
## var2 hi bits: r3

## Since we are working with 64 bit integers
## we have to distingush between the lower
## bits [0...31] and the higher bits [32...63]
## the resulting Lo bits are stored in r0,
## the resulting Hi bits in r1.
## To calculate the product of both values
## we need some tmp vars (r4...r7) for the
## higher bits

## make room for local temp vars
push {r4, r5, r6, r7, lr}

## r4  <-->  r_H = a_L × b_H + a_H × b_L + (a_L × b_L) / 2^32
## r0  <-->  r_L = a_L × b_L
mul r4, r0, r3
mul r5, r1, r2
umull r0, r7, r0, r2
add r4, r4, r5
add r1, r4, r7

## restore vars and jump back
pop {r4, r5, r6, r7, pc}

Schöne Grüße,

Cymatoxa


Edit: Sorry, hab mir angewöht, massig zu kommentieren ;D