-
06-07-2019 - |
문제
다음은 짧은 구현입니다 러시아 농민 곱셈. 어떻게 개선 될 수 있습니까?
제한 : A> 0, B> 0 일 때만 작동합니다.
for(p=0;p+=(a&1)*b,a!=1;a>>=1,b<<=1);
해결책
공백, 적절한 압입 및 적절한 기능 본문을 추가하여 개선 될 수 있습니다.
int peasant_mult (int a, int b) {
for (p = 0;
p += (a & 1) * b, a != 1;
a /= 2, b *= 2);
return p;}
보다? 이제 세 부분이 어떻게 for
선언이 사용됩니다. 프로그램은 주로 인간의 눈을 위해 작성되었습니다. 읽을 수없는 코드는 항상 나쁜 코드입니다.
그리고 지금, 내 개인적인 즐거움을 위해, 꼬리 재귀 버전 :
(defun peasant-mult (a b &optional (sum 0)) "returns the product of a and b, achieved by peasant multiplication." (if (= a 1) (+ b sum) (peasant-mult (floor (/ a 2)) (* b 2) (+ sum (* b (logand a 1))))))
다른 팁
나는 이것이 끔찍하다고 생각합니다 이것은 컴파일러의 관점과 정확히 같은 코드이며 (희망적으로) 훨씬 더 명확합니다.
int sum = 0;
while(1)
{
sum += (a & 1) * b;
if(a == 1)
break;
a = a / 2;
b = b * 2;
}
그리고 지금 나는 그것을 썼다. 나는 그것을 이해한다.
이것을 개선하는 정말 쉬운 방법이 있습니다.
p = a * b;
A 또는 B가 0보다 작을 수 있다는 이점도 있습니다.
그것이 실제로 어떻게 작동하는지 보면, 그것은 단지 정상적인 수동 곱셈이 바이너리임을 알 수 있습니다. 당신은 컴퓨터가 이런 식으로 내부를 수행하므로 (1), 러시아 농민 방법을 사용하는 가장 쉬운 방법은 내장 곱셈을 사용하는 것입니다.
(1) 아마도 더 소멸 된 알고리즘이 있지만 원칙적 으로이 알고리즘과 함께 작동합니다.
루프에는 여전히 곱셈이 있습니다. 곱셈 비용을 줄이려면 대신 사용할 수 있습니다.
for(p=0;p+=(-(a&1))&b,a!=1;a>>=1,b<<=1);
나는 다른 사람들이 말한 것처럼 특히 끔찍하거나 난독 화되거나 읽을 수 없다는 것을 알지 못하며, 그 모든 다운 보트를 이해하지 못합니다. 이것은 여기에 내가 "개선"하는 방법이 있습니다.
// Russian Peasant Multiplication ( p <- a*b, only works when a>0, b>0 )
// See http://en.wikipedia.org/wiki/Ancient_Egyptian_multiplication
for( p=0; p+=(a&1)*b, a!=1; a>>=1,b<<=1 );
이것은 코드 난독 화 콘테스트를위한 것입니까? 나는 당신이 더 잘할 수 있다고 생각합니다. 초보자에게는 무의미한 이름 대신 오해의 소지가있는 변수 이름을 사용하십시오.
p
초기화되지 않았습니다.
만약 무슨 일이 일어나는지 a
0은?
만약 무슨 일이 일어나는지 a
부정적입니까?
업데이트: 위의 문제를 해결하기 위해 질문을 업데이트했음을 알 수 있습니다. 코드가 명시된대로 작동하는 것처럼 보이지만 (오버플로 문제를 제외하고) 여전히 읽기 쉬운 것보다 여전히 덜 읽을 수 있습니다.
나는 그것이 불완전하고 읽기가 매우 어렵다고 생각합니다. 어떤 특정한 종류의 피드백을 찾고 있었습니까?
int RussianPeasant(int a, int b)
{
// sum = a * b
int sum = 0;
while (a != 0)
{
if ((a & 1) != 0)
sum += b;
b <<= 1;
a >>= 1;
}
return sum;
}
곱셈이나 분할없이 답변 :
function RPM(int a, int b){
int rtn;
for(rtn=0;rtn+=(a&1)*b,a!=1;a>>=1,b<<=1);
return rtn;
}