Problem 539. Fun Race

Created by AMITAVA BISWAS

Solve Later

{"relationships":[{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/document","targetMode":"","relationshipId":"rId1","target":"/matlab/document.xml"},{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/output","targetMode":"","relationshipId":"rId2","target":"/matlab/output.xml"}],"parts":[{"partUri":"/matlab/document.xml","relationship":[],"contentType":"application/vnd.mathworks.matlab.code.document+xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n<w:document xmlns:w=\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\"><w:body><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:t>Given two unary functions foo and goo.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:t>Check whether foo(0) runs faster than goo(0).</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:t>Output 1 if foo is faster, otherwise output 2.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:t>Please give the answer within 1/5 seconds.</w:t></w:r></w:p></w:body></w:document>"},{"partUri":"/matlab/output.xml","contentType":"text/xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\" ?><embeddedOutputs><metaData><evaluationState>manual</evaluationState><layoutState>code</layoutState><outputStatus>ready</outputStatus></metaData><outputArray type=\"array\"/><regionArray type=\"array\"/></embeddedOutputs>"}]}

Solve

Solution Stats

335 Solutions
39 Solvers

Last Solution submitted on Sep 05, 2020

Last 200 Solutions

Problem Comments

2 Comments

2 Comments

Richard Zapor on 15 Jun 2012

Very entertaining puzzle.
Hint to the frustrated, as I was:
This is a "noise" exclusion problem. The 1-sigma uncertainty in the time measurement is greater than the "true" time delta between foo and goo.

The test suite method is also vey well executed.

Rafael S.T. Vieira on 5 Sep 2020 at 19:46

Regardless of noise, the function sign should not be faster than the gamma function. The function Gamma is a factorial/integral calculation, while the function Sign requires looking at just one bit. Unless there is a way to evaluate the gamma function looking at just one bit, sign should be faster. I am guessing that someone's computer has optimization issues.

PS: The other two cases make sense str2num should be slower since it is working with strings, and calling a function that uses a function B should be slower than just calling the function B.

Solution Comments

Solution 2915620

1 Comment

1 Comment

Rafael S.T. Vieira on 5 Sep 2020 at 20:00

The function timeit takes care of any noise that may be when evaluating a function by running it several times and extracting the median of them all (doc timeit). Even so, the function gamma obviously looses.

Solution 202651

1 Comment

1 Comment

Claudio Gelmi on 11 Feb 2013

Indeed the solution is random...

Solution 118176

1 Comment

1 Comment

Aurelien Queffurust on 24 Jul 2012

since tic toc didn't give me results, I tried the cody size approach

Solution 68836

2 Comments

2 Comments

Aurelien Queffurust on 24 Jul 2012

I tried a lot of times this solution without sucess

James on 20 Feb 2013

As did I, even with 10,000 iterations in the loop. My problem was that gamma took longer than sign did, despite the test suite saying it shouldn't. After four or five tries, I had to add an ugly hack that checked if foo was gamma.

Good to know this method does occasionally work, though...

Problem Recent Solvers39

Problem Tags

Problem 539. Fun Race

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers39

Suggested Problems

More from this Author100

Problem Tags

Problem 539. Fun Race

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers39

Suggested Problems

More from this Author100

Problem Tags

Players