2
\$\begingroup\$

Write a program which, given two positive integers n and x, will display the n-th root of x (which is also x1/n) in decimal to an accuracy of 0.00001. The program must output the resulting number in decimal, and it must work for any two numbers n and x. The variables may be defined in the program, or they may be inputted by the user, but it must work for any two positive integers.

However:

  • You may not use any arithmetic operators or bitwise operators (including +, *, ^, >>, etc.)
  • You may not use any built-in math functions (such as pow(), sqr(), or add()).
  • No web requests; the program must be completely independent from all outside sources.

Although I tagged this , a program with more code that can do the job more than 1 second faster is better. A winning program will be faster than all the other programs by more than a second. Time differences of less than 1 second will be considered negligible. If two programs complete within a second of each other, then the one with less code wins.

\$\endgroup\$
  • 3
    \$\begingroup\$ This might be doable with string operations. For fastest-code, we need a way to measure the speed of the program. I would like to say, "My program is s times slower than a program that uses arithmetic operators." For this, it would help to have a benchmark program, in a common language like Python, that uses arithmetic operators. The program might need to loop so it is slow enough to measure. \$\endgroup\$ – kernigh Jun 15 '14 at 23:29
  • 1
    \$\begingroup\$ Is n always positive? If not, what should happen when the result is an imaginary number? \$\endgroup\$ – Ypnypn Jun 16 '14 at 2:20
  • 2
    \$\begingroup\$ Perhaps I am wrong, but this problem does not seem to be possible to me. \$\endgroup\$ – Kyle Kanos Jun 16 '14 at 3:06
  • 2
    \$\begingroup\$ Could you please clarify how you are going to score both by code length and speed? a) as kernigh said, please state how you will be objectively comparing runtimes b) is code length just the tie breaker? Because it's virtually impossible to get a tie for fastest code, unless you score by asymptotic complexity. If it's not the tie breaker, we need a formula how length and speed factor into a single score. \$\endgroup\$ – Martin Ender Jun 16 '14 at 7:24
  • 4
    \$\begingroup\$ @TimothySmith so you are aware that requires you to run all submissions on your own machine in order for timings to be comparable? \$\endgroup\$ – Martin Ender Jun 16 '14 at 18:50
2
\$\begingroup\$

JavaScript

This answer doesn't satisfy all the rules, but I'm happy that at least it works. It's valid only for integers greater than one and there's no further precision.

Note that the + and > operators are used for string concatenation/comparison and the maths is behind the curtain. I hope that the ! operator doesn't count as "arithmetic" as it operates over booleans.

function f(x,n){for(a=(c=',')+Array(x),s=r=c;a>s;r+=c)for(i='',s=r;i!=Array(n);i+=c)s=s.split(c).join(r);return r.slice(1).length}

And some tests:

> f(125,3)
5
> f(16807,5)
7
> f(4782969,7)
9
\$\endgroup\$

Not the answer you're looking for? Browse other questions tagged or ask your own question.