Yeah, that's not going to scale. In practice you test whether the number is a quadratic residue mod a few small integers. The first stage is to look at the number mod 256 i.e. examine the least significant byte. Then, for a 64-bit machine, test mod 5, 7, 9, 13, 17 and 97. This catches 99.62% of perfect squares very quickly. If the number passes the test you still need to verify it's a square which is expensive, but you only have to do it 0.38% of the time
Serious question - where do you learn stuff like this? Had an algorithmic programming class in college but never had to solve problems like this on the job. At a bare minimum, this is fascinating.
@@jackhedaya571 Do you mean me or the channel owner? If you're asking me, then the answer is many, many years using computers to solve number theory problems (I'm not a mathematician, but a mathematically-oriented software engineer).
@@davidgillies620 Yup! Was asking you. Saw the question and immediately thought there needs to be a super fast way of doing it (I was guessing it would be some bit magic). That's really cool! Can I ask what domain of software you work in? My day-to-day is mostly APIs, DBs, deployments, etc. but a part of me yearns to work on problems that require more clever solutions.
Best way to scale this solution is to see that # of digits in the sqrt(n) is the ceiling of 1/2 the digits in n. Then you can set your binary search range to 10000....99999 (with the number of digits determined by the relation described above). This is true for 100% of cases, no exceptions.
One optimization to the solution provided can be made by observing the fact that every number's square root has the property: # of digits in floor(sqrt(n)) = ceil (1/2 * # of digits in n). Therefore, instead of starting at 1/2 of n, you can safely have a range between 100.... to 999.... where the numbers have 1/2 as many digits as n (rounding up). For very small n, this won't help (but the process is really quick anyways). But for very large numbers, let's say 1000000000, you can start with a range of 10000-99999 instead of 1-500000000.
You can also start the range as 1 to N/2, the sqrt can't be bigger thaan half of the number for any number >= 4. And we can always do a sqrt(n) == floor(sqrt(n)), but I guess that could have a rounding error.
Yes but you can make it scale better at the cost of a little bit of overhead. 1. Squares of even numbers are always even and squares of odd numbers are always odd. Don't check even numbers when getting the square root of 121 but only check the odd ones. 2. If you have some idea of what range most of the numbers you want to check are then don't begin at 1² (actually, never begin at 1, it's always 1). If needed make a list where the ends are the range of most of your numbers and fill the rest with other numbers that allow you to get closer in fewer steps. When your result is between 2 of the numbers in the list then you start checking more closely. Alternatively you can take steps of 10 and square those, of your number is more than 100 but less than 400 you know it's root is between 10 and 20. Edit: 3. As someone else pointed out, you only need to check up to N/2 as the square can't be higher than that. But again, if you know your numbers are going to be large than you could try N/4 as any number larger than 4 would fall in that range.
Maybe it's dumb but you could lower the steps required in half if you check if the number is even or uneven. If it's even you know it can only be a square of even numbers. Similarly with an odd number. So just check between 1 to another odd large number or from 2 to an even number. And set the boundaries as L+2 or R-2
I think I have one of the fastest leetcode solutions for this one iirc. I cheated and used a taylor series expansion that's done using type coercion in C++ as an initial guess.
It'd probably be much faster to find the number of digits in the representation of the value, and just drop half of them and start you search there. So if N = 405332, don't start with 202666, but with 405. A binary search takes 3 steps to remove a digit from a decimal representation, which could be a lot of steps for a very large number.
I am thinking that you can scale all recorded speeds for segments down to a range (0,1] where 1 * speed limit gives you the absolute speed. Also, featurize the historical timestamps into day of week/month, year, season, holiday, etc for those 2 min segments for each day. From this, there are plenty of regression models that are fast enough to be able to put out a (0,1] speed given the features for the actual predicted period/road segment. You can train these on splits with multiple 2 month holdouts to do as many sessions of cross-validation for hyperparameter tuning as you like. Your loss function can be MAE/RMSE/etc for the 2 months of predictions. Each day, you batch create your predictions for the next day, and they are stored in a fast cache to be used with the existing shortest path function to calculate the ETA.
@@GregHogg Woops. This comment was supposed to go on a MLSD video. Was wondering why it didn't show up. I'll post an actually relevant comment in a new thread haha.
you can go from 1 to N/2 and check only those that have the same parity than N. that speeds it quite a bit for large numbers. there are other additional methods to speed it even more but are a bit more complex and it's late for me. good night.
In c++ its too easy, just create an int n, read n from console, calculate sqrt(n) - dont forget to include cmath, create a double variable m = sqrt(n) and of static cast m - n == 0 return true else return false
If you take a look at the perfect squares you'll notice their progression is as follows: 4-1=3 9-4=5 16-9=7 25-16=9 ... Those are the odd numbers. So if you want to check if any number is a perfect square you can check if it's part of this progression or not.
If the sqrt is not allowed simply use the representation of a sqrt which will always be ^(1/2), by doing so and validating if the number is a int, it’ll beat that since its complexity is O(1)
Sqrt operation is not O(1). If i ask you what the sqrt of an arbitrary number is you would need to do an increasing amount of work proportional to the magnitude of the number I chose.
@@njgskgkensidukukibnalt7372 But we assume the size of integer if fixed, e.g. 32bit, 64bit. So the magnitude of a number is constant. Without the assumption, even the method shown in the video will need to handle large numbers, or integers with arbitrary number of bits.
@@user-wt1ul7ki6p ? i dont understand. The code in the video (and for an integer sqrt program) does a binary search between 0 and n. This will take O(logn). The number of bits needed to represent the number is independent of the number of steps the binary search part will take. What matters is the magnitude of n which is not constant here.
In theory it wouldn't work for all N. there could be some N that is close enough to a perfect square that the decimals get truncated after enough places after the sqrt. and int() will truncate any float its given so you'd have to do something else like modulo division to check for decimals.
@@bobmike2373 then u could, instead of int(), just modulo divise the sqrt to itself floored. To do so, u would store the result of the sqrt in a variable so that u don't have to calculate it 2 times. If the result is 0, it is a perfect Square, else not
@@ryanzullo7169floor() is going to cause losses. you can just do: return (sqrt(N) % 1) == 0. This would work for the most of the reasonable amounts of values for N. sqrt() in code isn't actually a true sqrt() and is just an approximation using fancy math. Plus if N is very large, the amount of bits that sqrt() has access to will be limited. This bit limitation will cause errors for some N that are large enough and are close enough that the precision of a float number wont be able to tell the difference and will mislabel some numbers as squares.
It boils down to there being no pure integer square root CPU instructions under the hood - the simplest is the x87 fsqrt function which yields a floating point result with only around ~23 bits of precision. The bottom line here is that you cannot rely on floating point values because it require equality testing which is non-deterministic due to the lack of precision. Even if you use SSE (32bits of precision) or SS2 (64 bits), this fundamental constraint applies - you cannot be guaranteed that you have enough precision to guarantee a "perfect" square root. You could of course implement an integer sqrt function (for example Newton's or Heron's method) to appeal to the "understandability" of what you're trying to achieve, but since it is iterative it has a non-linear cost, which happens to be greater than this recursive approach.
How do you think square root function is programmed? For integers it would be programmed in a very similar way (same time complexity), and for floating point numbers you would have to use something like newton’s method which would be even worse
@@njgskgkensidukukibnalt7372 First of all, if you're using Python, the sqrt can be programmed inside the implementation of the interpreter, likely in C. In such tasks C is likely at least one order of magnitude faster (I'd guess 2 orders of magnitude because of extensive use of loops). Now consider the possibility (spoiler: actually the case) that the CPU can implement the function in the hardware. This is why maybe youtube shorts isn't the best place to learn programming.
taking the sqrt of a number is expensive. that’s why games do approximations instead of calculating the sqrt of numbers. or in cases where you don’t need to explicitly sqrt, you can instead multiply x*x as shown here which is a faster and very easy for computers to do.
Here's how i did it: def isPerfSq(a): return a**0.5 - math.floor(a**0.5) == 0 For any number a EDIT: I just realized it's probably better to check if a**0.5 % 1 == 0 but whatever it still works
just realized Math class probably isn't allowed so here: public boolean isPerfectSquare(int num) { int sum = num-1, x = 0; while (sum < num){ sum = x*x; if (sum == num) return true; x++; } return false; }
Btw, I offer personalized 1 on 1 tutoring services for data structures and algorithms / coding interview prep - please email greg.hogg1@outlook.com to book a meeting with me!
@@GregHogg perfect squares are made up of consecutive odd numbers. subtract until you hit 0 or less, if exactly zero then number is a square. There are likely optimisations and mathematical shortcuts
@@drcl7429how u gonna know the number to check if u got a square and not just even number? If u gonna check it your code is already slower than binary search
@@GregHogg I just thought I would contribute my solution to this comment section even though it shares the same time and space complexity with yours, being O(log n) and O(1) respectively.
The problem is that square roots and fractional exponents in general, aren't a very efficient algorithm. They are subject to floating point errors. You might have a near-miss case, where a square root APPEARS to be a perfect integer, but is off by 10^(-16), and it is a blind spot to your code if you use floating point math. The idea is to do this purely with integer operations.
