어셈블리에서 빠른 곱셈 알고리즘

저의 임무는 작은 프로그래밍 언어를 가짜 어셈블리 언어 (레지스터 및 메모리 셀은 정의되지 않은 길이 임)로 컴파일하는 컴파일러를 작성하는 것입니다. 내가 무엇을해야어셈블리에서 빠른 곱셈 알고리즘

는 명령 변환입니다 : 내가에게 지침을 ADD, INC, SHL 전 세트에

a = b * c

을하는 것이다 (내가 메모리에 대한 포인터이고, 하나 개의 레지스터를 사용할 수있다) 곱셈을 수행하십시오. 문제는 알고리즘이 O (log n) 시간 동안 작동해야한다는 것입니다.

누구든지이 문제를 해결하는 알고리즘을 단계별로 설명 할 수 있습니까? 제 친구가 Booth-Mcsorley 알고리즘을 언급했지만, 거의 이해하지 못했습니다.

편집 : 읽기, 쓰기,로드 i, 저장 i, 추가 i, 하위 i, SHR i, SHL i, INC, RESET, JUMP k, JZERO k, JODD k (k 레지스터가 홀수 인 경우)

출처

2015-01-05 TeoTN

condtition (asm 형식)이 허용되는지 또는이 세 명령 만 허용됩니까? 숫자는 2 진수 2의 보수입니까, 아니면 양수입니까? ...? – deviantfan

구시대 "고급 곱셈 알고리즘"은 부스 (동일한 비트의 실행 활용) 및 McSorley (기수 -4 변형)를 비롯한 하드웨어 구현을위한 것입니다. 표준 바이너리 알고리즘을보고, 친구에게 그녀가 무엇을 얻었는지 물어보고, _fake_ 어셈블리의 흐름 제어 및/또는 조건부 산술을 지정하여 시도가 얼마나 멀리 있는지 전 세계에 알리십시오. (나는'undefined length'가 2의 보수를 엉망으로 만들 것이라고 기대한다.) – greybeard

'O (log n)'의'n '은 무엇을 나타내는가? 'a','b'' 또는'c'의 크기는? 아니면 레지스터 비트 길이? 숫자 중 하나의 이진 표현에서 '1'비트의 수? 완전히 다른 것? 나는 당신이 물어 보는 것이 레지스터 비트 길이에 대해'O (n)'또는 여러분이 곱하려고하는 숫자 중 하나의 크기에'O (log n)'을 할 수 있다고 생각합니다. – twalberg

이것은 가짜 어셈블러이므로 왜 속도가 중요한지 궁금합니다. 오른쪽 연산 피연산자의 크기에 비례하는 길이의 순진한 반복 알고리즘을 구현하지 못하도록하는 것이 더 쉽습니다 (또는 간단한 최적화를 원할 경우 두 피연산자 중 작은 값을 사용하지만 O (n) 그럼에도 불구하고).

곱셈 명령어 부족 명령어 세트에 승산 실행 방법은 쉬프트 및 부가 (이진 본질적 긴 승산)를 사용하는 것이다. 당신이 제공 한 지시 사항을 감안할 때, 이것은 가장 가능성있는 해결책이라고 생각됩니다.

이 질문은 How can I multiply and divide using only bit shifting and adding?과 관련이 있습니다. C에서 O (log2 n) 인 shift + add 구현은 What is the time complexity of this multiplication algorithm?에 대한 응답으로 표시되지만 명령 집합에 맞게 조정할 수 있습니다.

출처

2015-01-05 11:26:05 Clifford

어셈블리에서 빠른 곱셈 알고리즘

답변

관련 문제