Forum Discussion
Lambda for Prime Numbers in a Range
So I need to get prime numbers to calculate Modulo 1021 for check characters on a UDI. So I decided to create some Lambda functions. I found some old Excel formula/code on the internet that I fixed some errors in and converted to some of the new available functions:
=LAMBDA(low, high,
LET(
rng, SEQUENCE(high - low + 1, 1, low),
rngo, SEQUENCE(1, INT(SQRT(high)), 2),
list, IF(
MMULT(
--(IF(rng > rngo, MOD(rng, (rng > rngo) * rngo)) = 0),
TRANSPOSE(rngo)
) = 0,
rng
),
FILTER(list, list, "")
)
)
this was already an improvement over the original code because a) it fixed a problem with the original using too small a range that it could identify non-prime numbers as prime and now only checks numbers up to SQRT(high) . But easy improvement was to check only odd numbers but also had to check the number 2 (i.e. a prime must be an odd number except for 2) so:
=LAMBDA(low, high,
LET(
rng, SEQUENCE(high - MAX(2, low) + 1, 1, MAX(2, low)),
rngo, SEQUENCE(1, MAX(INT(SQRT(high) / 2), 1), 3, 2),
list, (MMULT(
--(IF(rng > rngo, MOD(rng, rngo)) = 0),
TRANSPOSE(rngo)
) = 0) * (ISODD(rng) + (rng = 2)) * rng,
FILTER(list, list, "")
)
)
ok that worked and then I tried another improvement to replace MMULT with BYROWS(...LAMBDA()):
=LAMBDA(low, high,
LET(
rng, SEQUENCE(high - MAX(2, low) + 1, 1, MAX(2, low)),
rngo, SEQUENCE(1, MAX(INT(SQRT(high) / 2), 1), 3, 2),
list, BYROW(IF(rng > rngo, MOD(rng, rngo), 1), LAMBDA(in, AND(in))) *
(ISODD(rng) + (rng = 2)) * rng,
FILTER(list, list, "none")
)
)
So I did some speed checks on this and please tell me if there is a better way but I used the following formula:
=CHOOSE({1,2,3},NOW(),PrimesRange(1,100000),NOW())
and then in another cell I did a difference between the 2 NOW() cells
So the 1st Lambda took an average of about 10s
the 2nd Lambda was 3.8s
the last Lambda variation was 2.9s
This has a been a great teaching experience for me (including learning why I want to be careful using the IFS() statement and probably will go back to using nested IF() more often, thank you Joe User ) but I am also hoping to learn more and know if some colleagues here (e.g. @Sergei Baklan , @Riny_van_Eekelen , @Peter Bartholomew , @Hans Vogelaar , @NikolinoDE , and many others) can help me further improve the efficiency. or even learn a better way to time test my functions.
thank you
5 Replies
- mtarlerSilver Contributor
OK so I can't believe I didn't think of this sooner. I just reduced the time in 1/2 again by only looking at the odd numbers so now the sequence of numbers in the range of interest will only be the odd numbers but I did have to play with it a bit to include the number 2 in the end if needed so hopefully someone can improve on that. Here is the updated LAMBDA with a time mark of 1.5s for 1-100,000:
=LAMBDA(low, high, LET( rng, SEQUENCE( (high - ISEVEN(high) - IF(low < 3, 1, low + ISEVEN(low)) + 2) / 2, 1, IF(low < 3, 1, low + ISEVEN(low)), 2 ), rngo, SEQUENCE(1, MAX(INT(SQRT(high) / 2), 1), 3, 2), list, BYROW(IF(rng > rngo, MOD(rng, rngo), 1), LAMBDA(in, AND(in))) * IF(rng = 1, 2, rng), FILTER(list, list, "none") ) )
all these improvements also improve the range it can be used on. the original would error out due to resources but the newer ones I could run on 1-200,000 with times: 11.5, 9.8, 4.3s respectively and then only this last version would run on 1-300,000 which took 7.7s and found 25,997 prime numbers can that even be right? Now I'm questioning if I'm running into calc errors in excel...
- PeterBartholomew1Silver Contributor
I had a run through for ideas. I got to BYROW/MOD/AND but found you were there ahead of me.
You halved the count of numbers to test by eliminating even numbers. A further reduction could be to remove multiples of 3 as well by generating numbers
= LAMBDA(low,high, LET( k, SEQUENCE(QUOTIENT(high-low,3),1,1+MROUND(low,6),3), k+ISEVEN(k) ) )
Another thought is to perform the extraction in tranches. For example, to identify primes in the range 32-1000 you only need to test against the 10 primes in the range 2-31. That is not too exciting but, for the next tranche 1,000-1,000,000, you only need to test against the ~144 primes over 2-997 that you have already found.
As for timing, I use Charles Williams's functions that time calculations to μs.
I carried out the 3-step process and took 5sec to determine 78330 supposed primes between a thousand and a million. My active range wen to FR333002 which is probably a cell I have never seen before. It was probable a mistake to lay the test primes out as a row array. Both could have been columns if I were to use MAP rather than BYROW for the modulo calculation.
= FILTER( number#, MAP(number#, LAMBDA(n, AND(MOD(n,prime)))))
Note: This did improve the used range,
- mtarlerSilver Contributorjust a quick update. I incorporated your concept of counting by 3 instead of 2 but had to tweak it a bit (I will post the updated code later) and happy to say it cut the timing in half again. Now that is done, I hope to use it and try a recursive solution.