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\$
-1
\$\begingroup\$

A simple try

This might be not the idea of the task, but it should hold the rules and works.

I'm sorry, I had to use WolframAlpha, wich I'm not able to proof if it uses web recources (but that the programm itself is a web resource is not forbidden ;-), but I uninstalled ILog a few days before so I couldn't use it. Also it just omits the *, but it's indirectly used.

The idea is, to use an optimizing language wich allows to omit the *, wich is just syntactic sugar.

solve 137=a a with 10 digits
\$\endgroup\$
  • \$\begingroup\$ Btw: is &(bitwise and) and |(bitwise or) allowed? Then I do have an other idea. \$\endgroup\$ – thi gg Jun 27 '14 at 20:39
  • \$\begingroup\$ No, & and | are not allowed. \$\endgroup\$ – Timothy Smith Jul 1 '14 at 23:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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