+ 5

how to deal with large numpy arrays

My problem with this code is that it creates two very large np.arrays for n = 123567101113. One for the numbers in the form x^2+1 and one for the squared primes. For the prime numbers I can maybe use sympy.nextprime(), but I don't know what to do with the nums array. Can I swap them out somehow? My idea would be to make np.array chunks and process as much as possible at the same time. a) can you store np arrays externally? Or should I put the numbers in a file? b) is it possible to process np arrays in parallel? c) the size of the numbers within the array should not necessarily be a problem, should it? d) does nextprime() or primerange() have a limit? Thank you very much! https://sololearn.com/compiler-playground/c0AJ4Fpl5dZd/?ref=app https://sololearn.com/compiler-playground/c0AJ4Fpl5dZd/?ref=app

3rd Dec 2023, 3:11 PM
Denise Roßberg
Denise Roßberg - avatar
13 Answers
+ 4
A quick search I found numpy support parallelism, and it seems the playground support it. https://superfastpython.com/numpy-multithreaded-parallelism/ However I'm much more eager to know why C(10) = 9 and C(1000) = 895 or how it is calculated?
4th Dec 2023, 1:45 AM
Wong Hei Ming
Wong Hei Ming - avatar
+ 3
The problem of large arrays was avoided in ai. Perhaps you could design the calculations in a similar way.
3rd Dec 2023, 5:02 PM
JaScript
JaScript - avatar
+ 3
Wong Hei Ming This video could be interesting for you: https://youtu.be/Qgevy75co8c?si=SHBN1_g-2Z9PJDWI while loop is slower than a for loop. And the best thing is to avoid own loops if you can by using in-built functions.
5th Dec 2023, 3:07 PM
Denise Roßberg
Denise Roßberg - avatar
+ 2
Denise Roßberg I'm a bit dumb and not fully understand your task at hand. As I see, C(10) can be express in this way def C(num): res = [] for i in range(1, num+1): res.append(i**2 + 1) print(res) [2, 5, 10, 17, 26, 37, 50, 65, 82, 101] There are 10 elements in res, only 50 is not a square free number. So, C(10) = 9 means "there are 9 numbers are square free", am I correct?
4th Dec 2023, 4:54 AM
Wong Hei Ming
Wong Hei Ming - avatar
+ 2
Wong Hei Ming The range in the second code was wrong. I fixed it. And as I mentioned I used 1,2,3,4...n (just for demonstration). So it gives you all square free nums in a range not only such in form x^2+1
5th Dec 2023, 12:54 PM
Denise Roßberg
Denise Roßberg - avatar
+ 2
Denise Roßberg The video is interesting and clear my doubt: is more function call increase the running time? And I do admit I lack of knowledge of built-in / 3rd party modules. However day 5 quiz in part 2 the input is insane for me. It gives 10 sets of data, each set contains a range, in total there are 2,504,127,863 values. For each value it has to go through 7 set of tests. Each set has 1x to 4x sub statement to check against with. If the value gives a True it moves on to the next set early, otherwise it has to check all the sub statement before moving on. And I can't find a "known in advance" pattern in it. About your task on hand I can't think of any method can solve it within a minute or two. I guess it might have something to do with bitwise operation.
6th Dec 2023, 4:08 AM
Wong Hei Ming
Wong Hei Ming - avatar
+ 1
Wong Hei Ming A square free number is not divisible by a square number > 1: e g. 10 is square free because 2*5 12 is not square free because 2*2*3, so it's divible by 4 https://oeis.org/A005117 But you need to find square free numbers of the form x^2+1 (2,5,10,17...) For n = 10 you have the numbers from 2 to 101 and 50 is the only number which is divisible by 25 So C(10) = 9 Hope this helps.
4th Dec 2023, 4:18 AM
Denise Roßberg
Denise Roßberg - avatar
+ 1
Wong Hei Ming Yep, that's right. And don't feel dumb. It took me also a while to understand the task 😉
4th Dec 2023, 5:58 AM
Denise Roßberg
Denise Roßberg - avatar
+ 1
I'm feeling dumb because I joined Advent of Code like this. https://www.sololearn.com/post/1749692/?ref=app Here is an idea while I'm not familiar with the technique. We turn it into a generator and check each number is square free or not. If it is not, minus 1 from the original input.
4th Dec 2023, 6:20 AM
Wong Hei Ming
Wong Hei Ming - avatar
+ 1
Denise Roßberg Maybe I use your code wrongly, when I enter 10 & 10, it produces 2 different results and they are not 9. It is my approach as I described earlier. https://sololearn.com/compiler-playground/co18g01x8F1a/?ref=app Apparently it can't handle large number as yours. But it is my best while it don't throw a "memory error". And I'm curious how to handle large amount of data. It is one of the problem in today's advent of code quiz.
5th Dec 2023, 12:45 PM
Wong Hei Ming
Wong Hei Ming - avatar
0
Wong Hei Ming This is how I approached it: First I looked at the divisors to see if there were squares in them. But divisors are made up of the prime factors, so you just have to check whether each prime factor only occurs once. Knowing that sympy only returns unique prime factors, I thought it would be enough to check whether the product of the prime factors is equal to the number to be checked. If time doesn't play a role, you can even write this as a one-liner (not counting the imports). https://sololearn.com/compiler-playground/c5DI5kPLhA87/?ref=app Another approach (but only works for 1,2,3...n): If a prime factor occurs twice, this is nothing other than a squared prime number: 2*2 = 4, 3*3 = 9, 5*5 = 25, etc. So in principle, you only have to think about how many numbers are divisible by 4, 9, 25, etc. n = 20 20//4 - 20//9 = 13 Here you just have to be careful not to take numbers twice if they are divisible e.g. by 4 and by 9 .
4th Dec 2023, 3:20 PM
Denise Roßberg
Denise Roßberg - avatar
0
Denise Roßberg Oh...rushed and didn't read the comments......
5th Dec 2023, 12:56 PM
Wong Hei Ming
Wong Hei Ming - avatar
0
Can you reply the follow up?
6th Dec 2023, 3:00 AM
Ibrahim Benaouina
Ibrahim Benaouina - avatar