o (1)(a)Devise an algorithm to find the fifth root of N, where N is any positive perfect fifth power.
o (1) (b) How about deriving an algorithm corresponding to the case where N is a positive integer but NOT a perfect fifth power?
o (2) Extend (1) by devising an efficient algorithm to cover the general case where N is any positive real number.
While there is an algorithm similar to the square root algorithm, where the digits are blocked off in groups of 5 rather than the groups of 2 when doing square roots, but otherwise works analogously, that's something that was not devised by me, so is not my solution. Anyone interested can find the nth root algorithms on Google or Wikipedia.
But mine is a not-very-efficient binary search:
while true
x=input("Number:");
if x<0
signflag=true;
x=-x;
else
signflag=false;
end
if x<1
rcpflag=true;
x=1/x;
else
rcpflag=false;
end
low=0; high=x; y=x/2;
flag=0; iter=0;
while y^5~=x && low<high
power5=y^5; iter=iter+1;
if power5>x
high=y;
y=(low+high)/2;
elseif power5<x
low=y;
y=(low+high)/2;
end
if abs(y^5-x)/x<1e-15
flag=flag+1;
if flag>3
break
end
end
end
if signflag
y=-y;
x=-x;
end
if rcpflag
x=1/x;
y=1/y;
end
if round(y)^5 ==x
y=round(y);
end
% disp([x y iter])
fprintf('%16.15f %16.15f %3d\n',x,y,iter)
end
The binary search is surrounded by checks for negative values or values whose absolute value is under 1, where the argument is negated or made into its reciprocal, the effects of which are undone at the end to get the correct answer.
>> fifthRoot
Number:243
243.000000000000000 3.000000000000000 53
Number:-243
-243.000000000000000 -3.000000000000000 53
Number:1/243
0.004115226337449 0.333333333333333 60
Number:-1/243
-0.004115226337449 -0.333333333333333 60
Number:77
77.000000000000000 2.383955503454899 59
Number:-77
-77.000000000000000 -2.383955503454899 59
Number:1/4
0.250000000000000 0.757858283255199 55
Number:1/2
0.500000000000000 0.870550563296124 54
where the input number is repeated followed by the fifth root found and then the number of iterations of the binary search. It's clearly not optimal.
Also, it was designed for the approximately 15 or 16-digit accuracy of most computer systems, not for manual computation.
|
|
Posted by Charlie
on 2022-09-29 08:35:46 |
a suboptimal algorithm
