Assembler mnożenie liczb

0

Witam,
Mam do zrobienia w assemblerze poniższe zadanie:
"Napisz program, który policzy iloczyn dwóch liczb 256-bitowych (lub 128- bitowych dla architektury 32-bitowej). Wykorzystaj algorytm mnożenia pisemnego rozszerzając go z cyfr dziesiętnych do liczb 64-bitowych (32-bitowych)".

W związku z tym mam do was kilka pytań:

  1. Jaki jest zakres liczb 256 bitowych? 2^256 ?
  2. Mógłby ktoś mi przybliżyć jak ten algorytm ma mniej więcej działać? załóżmy mamy dwie liczby x oraz y. Co dalej z nimi robimy?
  3. Jakieś wskazówki jak zaimplementować to w assemblerze?

Dzięki

1
  1. Tak, jeśli mówimy o liczbach bez znaku.
    (Dla 64-bitów) Potrzebujesz wykonać mnożenie dwóch 256 bitowych liczb. Więc w rezultacie otrzymasz liczę 512 bitową.
  2. Mnożymy je. Tak jak robisz to na kartce w notacji dziesiętnej tak tutaj w notacji binarnej.
    Jak możesz zauważyć mamy tylko dwie możliwości (0 i 1), więc 0 daje nam zawsze 0, a 1 liczbę, którą mnożymy.
    Więc aby pomnożyć jedną przez drugą, trzeba dodawać liczbę pierwszą do wyniku, jeśli jest jeden (jeśli zero to nic nie robić) i po każdej pętli przesuwać wynik w lewo o jeden bit (albo w prawo - sprawdź sam :) ).
  3. Możesz to zrobić za pomocą instrukcji ogólnego przeznaczenia. Możesz też wykorzystać MMX.
    Ogranicza Cię tylko Twoja wyobraźnia.

Proszę

3
Kordoba napisał(a):
  1. Jaki jest zakres liczb 256 bitowych? 2^256 ?

Liczymy od zera więc górny zakres dla 256 bitowej liczby bez znaku to (2^256)-1

2

Jeszcze przykład mnożenia:
1010 = 10
0110 = 6

0000 0110 - zapis w rejestrze(miejscu) wynikowym

0000 0110 - dodatnie 0 (bo w 0110 - na końcu jest 0 - rozpakowujemy liczbę 6)
0000 0011 - przesunięcie

1010 0011 - dodanie 10 (bo w 011 - na końcu jest 1)
0101 0001 - przesunięcie

1111 0001 - dodanie 10 (bo w 01 - na końcu jest 1)
0111 1000 - przesunięcie

0111 1000 - dodanie 0 (bo w 0 - na końcu jest 0)
0011 1100 - przesunięcie (= 60)

W wyniku mamy liczbę 60.

0

Dziękuję wam za odpowiedzi. Jeszcze zastanawia mnie to zdanie
"Wykorzystaj algorytm mnożenia pisemnego rozszerzając go z cyfr dziesiętnych do liczb 64-bitowych (32-bitowych)"
O co może chodzić o "rozszerzenie" i dlaczego do 64 bitowych liczb, a nie do 256 bitowych? Przecież mnożymy takiej wielkości liczby

1

Bo operacje w asemblerze masz tylko 64 bitowe

0

W tym wypadku gdy mam 128 bitowe liczby, muszę je przechowywać w 4 rejestrach eax... ? jeśli chcę robić na rejestrach ogólnego przeznaczenia?

1
Kordoba napisał(a):

W tym wypadku gdy mam 128 bitowe liczby, muszę je przechowywać w 4 rejestrach eax... ? jeśli chcę robić na rejestrach ogólnego przeznaczenia?

Nie ma 4 rejestrów eax. rejestr eax jest tylko jeden.
Mało ważne gdzie to będziesz przechowywać, chociaż rejestry mogą się szybko skończyć i będziesz musiał trzymać to w pamięci. Ważniejsze jest to że musisz mnożyć fragment po fragmencie.
Np jak chcesz pomnożyć liczbę A * B oraz A składa się z fragmentów A1, A2, a B składa się z fragmentów B1 B2, gdzie te z fragmentem 1 są bardziej znaczące to masz algorytm:

C1 = A1 * B1
C2 = A1 * B2 + B1 * A1 + przeniesienie z tego co nie zmieściło się w C1
C3 = A2 * B2 + przeniesienie z tego co nie zmieściło się C2

Czyli algorytm ten sam co przy mnożeniu pisemnym tylko zamiast cyfr masz liczby 64 bitowe

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0