Alright 64Digits, show me your stuff. I will describe three programming situations, and you will describe, or write, the most efficient algorithm for each situation. Most efficient answer wins. Anything goes, but no punches below the belt.
You can give me your answer in words, or give it to me in any language if you feel that is easier.All questions have been devised by me, although they aren't that original.Situation 1:You are given a positive integer and must find out if it can be created by the factorial of a positive, integer number.Details:A factorial of a positive integer number is the number multiplied by all integers below it.Situation 2: You are given a million integers in the range 0 to 100. You must output them numerically sorted, least to greatest.Details: Assume the integers are coming from some input function, and you are printing your result in some output function.Situation 3:You are given the 2D dimensions of a box, and then the dimensions of a smaller box. Taking into account 90 degree rotations (that is, exchanging the width and height of the smaller box), what is the largest amount of smaller boxes that can fit in the area of the bigger box?Details: Your algorithm should waste as little space as possible. No two smaller boxes are allowed to touch. No smaller box is allowed to go out of the bounds of the bigger box.Do any of the situations you please, I will announce winners by situation next blog.
@sixwinged no point in flooring it since that wasn't the original number :P
@meow44 - I think you may have missed the point. The original number is being constantly divided, eventually it will reach a number that is 1 or less. If the number reached is 1 we can say that the original number can be created from a factorial. The floor business is to attempt to quit the loop early if it can be determined that the never will never be equal to 1 when dividing by whole numbers. That is, if the number is not a whole number.
Java based solution for Situations 1 and 2 coming up :D
well I'm not going to argue anymore but I think it would eventually equal zero not 1
If you take the square root of any number greater than 1 constantly, you will never get anything below one. Ever.
This is because any positive decimal number below zero squared is a number smaller than itself, while any number above one is greater than itself when squared.Easy proof: First off, a^x is 1-1, meaning only one input per output. No vertical asymptotes.
a^0 is 1 in all cases a!=0.a^1=a in all cases a!=0if a>1, and the function is 1-1, then there are no holes, and the range between the powers of a^0 and a^1 (Where you start taking roots) is (1,a), meaning a square root, or any root, where a>1 will not ever touch a.I exit after return because in GM it helps efficiency, and in Delphi, the result is a variable.
@Kenon - I designed it for GM. GM has approximately equal efficiency for all commands. Even with a small decrease in efficiency because of the modulo, my algorithm should be more efficient in almost all cases other than a positive outcome, due to an early termination.For the record, by efficiency I don't mean "Whatever code runs the fastest", I mean algorithm efficiency - does your idea take steps that are unnecessary. Like, the situation using ds_list sort would be very inefficient because it does not take advantage of the format the numbers are presented in. It would be very slow of course, but that isn't the main issue.
So don't worry about divide versus modulos and all that, because GM will be slower than C++ any day, and I'm getting C++ entries from sk8. So it's not like I can judge it by running time.A very optimized assembly macro for FASM for situation 1, just because I can:
@ludamad - Your code is essentially mine, only using the assembly language to perform division and modulo at the same time. This does remove the multiplication part of mine, but it is not significantly different.