1 kyu

Express number as sum of four squares

71 of 114dolamroth
Description
Loading description...
Performance
Algorithms
Mathematics
View
AllIssues2Questions4Suggestions2Show Resolved
  • Please sign in or sign up to leave a comment.
  • towc Avatar

    This comment has been hidden.

  • anter69 Avatar

    My (rather simple) algorithm can do 2^128 numbers in basically no time, except for some special numbers. But above 2^200 it starts to struggle... Any hints? :-/

  • Qexo Avatar

    Been sitting for a while now. Tried everything I knew, even lagranges and legendres theorems (iterative reduction too), which work perfectly fine, passes all cases but takes a lot of time. Im failing with the timeout. Tip for others: Do not try to bruteforce and avoid deep recursion, takes a lot of resource and time so not efficient.

  • Mafir Avatar

    This comment has been hidden.

  • RootByte Avatar

    bro timeout always no fails but timeout

  • mikolainer Avatar

    At the beginning I tought this kata was about implementing arithmetic operations for big numbers. Then I saw that some cases had many solutions (which had more than 4 items) and I supposed that it's about some kind of bruteforcing the solutions... And it works for tests on "small" inputs. But I can't find a quick enough solution. So it seems that I should know something more about math to solve the kata. Also I didn't see any examples or simple explanations of the possible algorythm. Maybe once I'll come back with the secret knowledge.

  • cplir-c Avatar

    I guess integer factorization is too slow to help with this on the huge numbers...

  • Harold2017 Avatar

    i've tried my knowledge of checking 2/3/4 squares sum but still failed with realy big random tests.. any tips?

  • kulesh2023 Avatar

    This comment has been hidden.

  • AnyZver Avatar

    My program works with all numbers, but does not converge in time, I don't know how else to improve the program. Does anyone have any ideas...

  • Quark Fox Avatar

    My cheap trick did do better than my hard work, it was 28 now i cannot even pass the initial barrier!!

    i know its kyu 1 and nobody would help, i dont know if an experienced programmer'll consider wierd, but i did what i could , but some 20-21 digits later it doesn't work, i thought is either it should work entirely or not work at all (could be slow, thats a different issue), but how can it lose its precision !!! i feel i am missing some basic!! if someone generous, give me some advice or reffer to some other kata that may help, i'll be pleased.

  • Quark Fox Avatar

    This comment has been hidden.

  • Conrad_123 Avatar

    When trying to calculate the square root of a very large number I keep getting values a hundred or so too large. I've tried int(math.sqrt(num)) and int(num**\0.5). Is there another way to do this in python?

  • Baranovskiydev Avatar

    This comment has been hidden.

  • benjaminzwhite Avatar

    Thank you @dolamroth for this amazing kata, I have been unable to solve anything else on Codewars the past few days as I wanted this to be my 1111th solved kata - now I am finally free (until 2222 at least)!

    In addition, thank you for the "honeypot" for attracting interesting Codewars number theory users to conveniently follow; some of their solutions are incredible learning materials also.

    Thanks again for your effort in bringing this to CW :+1:

    edit- just noticed that I am 36th = 3**2 + 3**2 + 3**2 + 3**2 solver, the numerology is too powerful O_o

  • yeralexey Avatar

    ahaha, i managed to pass big random test, but really big - fails me)))))))))) am i close?))))))))))))))))))))

  • Temkash Avatar

    Fixed mistakes with degree (1\2) on huge numbers by couple of "-1 while number**2>n" (uncorrect count), but no way I can pass really big numbers by time limit. May I have some recommendations?

  • lachesism Avatar

    Hi,

    Nice kata, but IMO the current tests are not really debugging friendly.

    • If the user's answer has the wrong type, the error message is simply Expected False to be True.

    • having four assertions for one test case is confusing, so I suggest combining these assertions into one, like the following.

    error_msg = None
if type(a) is not int: error_msg = "some useful message"
#same for b, c, and d
if a * a + b * b + c * c + d * d != i: error_msg = "some useful message"
if error_msg is not None:
    test.fail(error_msg)
else:
    test.pass_()

    • add small random tests to help users test the correctness of their programs, as the current random tests are too big to debug.

    • make sure that static tests are consistent across sample tests and full tests.

  • dolamroth Avatar

    Updated reference Java solution, which used to timeout on certain inputs.

  • Voile Avatar

    The random tests are pretty weak. Because all the marbles are inside a single 2048-bit test the total runtime totally depends on what kind of number it is, and so the performance test is very luck-based.

    I think you should modify it like this:

    • A lot of small random tests to ensure correctness
    • More random tests with smaller numbers of all types to ensure performance
  • Voile Avatar

    This comment has been hidden.

  • raulbc777 Avatar

    This comment has been hidden.

  • raulbc777 Avatar

    Which are huge numbers for you? :)

  • dfhwze Avatar

    Performance tag should be added, and perhaps also the bounds of n stated in the description.