Hi, and welcome to RC :-)
(It's nice to get language authors contributions).
Hi, your permutations example seems to be written to answer more than one task but in doing so becomes a not very good RC code example for those tasks as it shows extraneous answers and code not needed in the task. Far better if you used a library or module import system and tailored each example to the task at hand. I have flagged these examples for attention as I don't think it would be good for RC tasks if this unrelated output from examples was to spread.
Thanks, I assume you meant the deranged anagrams task, which I have fixed. --Pete Lomax (talk)
I've uploaded http://phix.is-great.org/geshi/phix.php (which just gives you a blank page) to http://phix.is-great.org/geshi/phix.zip in case that helps --Pete Lomax (talk) 08:35, 15 September 2015 (UTC)
I've noticed that you've reposted the off-site link to Phix code for Boids. Is there no possibility to post this code on-site? This is after all the whole point of the wiki. Not only because it allows easy code comparisons, but also because it makes it possible for people to change the code. Also all code on Rosetta is posted under the same license. And links can become broken. Rosetta Code really isn't intended as a link directory. Fwend (talk) 14:26, 6 June 2017 (UTC)
- OK, done. I also added a screenshot, trust that is acceptable as an off-site link ;-) Pete Lomax (talk) 10:37, 7 June 2017 (UTC)
Use of Factorization Wheels in Sieves
As per the comment you made in your contribution to Extensible_prime_generator#Phix, you said "I investigated the use of so-called "wheels", beguiled by the claim that "a 2-3-5-7 wheel saves 77%", until I realised the breakdown was 2: 50%, 3: 16%, 5: 7%, 7: 4% - it is unthinkable not to exclude even numbers, the added complexity (and subscripting) of a 30- or 210- element wheel does not seem worthwhile."
With respect, you are missing something: While it is true that for extremely large ranges of prime approaching infinity, the majority of the gain is derived from using only the low number wheel factors, the benefit is much greater than expected for commonly used ranges. As per this link to the Wikipedia Sieve of Eratosthenes formula and tables, there is a reduction of a factor of about 2.67 using odds-only but a further factor of about 4.16 using the extra 3-5-7 wheel for a sieving range of a hundred thousand as is the requirement of the task, and a factor of about 2.5 for odds-only but a further factor of an extra about 3.26 for a range of about a billion as you calculated (actually you calculated to about two billion). In addition, it is fairly easy to implement pre-culling of the array(s) for the even larger wheel of 11-13-17-19 for a further smaller gain.
You further mention added complexity in subscripting, which isn't necessary; While it is true that there is added complexity in a page segmented version such as this in computation of page start addresses per prime, the actual subscripting for the culling operations doesn't need to be any more complex than for the odds-only case, which could be considered to be just one of the modulo planes out of the total of 48 used for 2-3-5-7 wheel factorization. Part of your perceived subscripting complexity may be because you didn't realize the optimization of reduced memory use using factorization: you can actually reduce the size of your "sieve" culling array by a factor of two as the even values aren't used; a further similar reduction of over a further factor of two is gained by extended wheels, with only the added complexity of starting addresses required at the beginning of each page.
BTW, about 27.5 seconds to calculate the 100 millionth prime for odds-only isn't particularly fast: even using odds-only Julia can calculate this range about ten times faster using an equivalent page segmented technique, as it looks like the techniques of the bit operations required to do bit packing by bytes to make maximal use of the CPU L1 cache are available in Phix, which reduces memory use by a further factor of eight; this is without the more complex techniques of implementing modulo bit planes for efficient wheel factorizations as discussed above for a further reduction of about four times, then multi-processing can be added... --GordonBGood (talk) 05:25, 13 November 2018 (UTC)
- Sorry for not getting back sooner, just before you posted my internet went down, and stayed that way for nearly a pigging month.
- I took another look, and concede that I am probably missing something, but still not quite convinced. Anyway, looking forward to seeing your first phix contribution :-)
- FYI, my mention of subscripting is biased by my internal knowledge of the workings of phix. While it is heavily optimised, and rarely any cause for concern, phix is reference-counted and checking whether we need to do any reference counting can put it at a disadvantage when pitted against C-based subscripting, plus although I inline whenever possible, sometimes subscripting involves a call/return which C-based languages never do. Also, I did not mean subscripting the sieve, but was referring to the subscripting of the wheel itself.
- BTW, running the latest julia code, the Euler problem 10, after correcting a typo, I found it was about the same time as phix, whereas the older julia code (plus one extra line and a few global directives so it would actually run) took over seven minutes to display the 100,000,000th prime - 15 times slower than phix, looks like the standard "using Primes" could be improved somewhat. However, the one billion bench from the Page Segmented Algorithm was indeed about 18 times faster. Maybe one day I'll find the time to give that method a spin, unless you beat me to it. --Pete Lomax (talk) 15:50, 16 December 2018 (UTC)
- No problem about not getting back; I posted this to you to maybe help your understanding of the Sieve.
- As to my use of your Phix language, it probably won't happen anytime soon as I have a toolbox full of languages and although it looks to be quite simple, I don't know about working around its limited data types. One thing I would really miss is the notion of first class function/procedure type as that would then allow one to defer execution, define lazy types, and not be so reliant on memory consuming large sequences. I see this, just as about anything else, can be worked around, in this case by using call id's, but it certainly isn't that beautiful as compared to languages that are designed to be more functional. I see that just about anything is possible in Phix, but I also wonder what kind of performance we might get if we do all of that.
- From your documentation, it isn't clear to me about the internal memory structure of sequences; is it a linked list or a simple array in memory? I assume you lose the extra MSB of integer to be able to distinguish between atom/integer... At any rate, any limitations on the use of sequences could be worked around by direct memory manipulations, again at the cost of beautiful code.
- On the other hand, although Julia isn't at all my favorite language and I don't really like dynamic typing, it can be quite fast for doing a lot of things, but even at that it isn't usually my language of choice for any job at hand.
- The "older Julia code" for the Extensible Generator isn't my code, and I just added a couple of alternate versions as I perceived its deficiencies. However, although the prime probability test that the Primes library uses is less complex and faster than testing for individual primes using trial division as some libraries do, it isn't really meant to be used as a generator of a sequence of primes. I think that you'll find that my alternate 1 is almost as slow although it better satisfies the requirements of being a true generator (in only one line of code).
- If you didn't have this limitation, you could implement "bit packing" and thereby achieve better cache locality in page segmentation as one CPU L2 cache size of say 16 Kilobytes could then contain 131,072 prime representations instead of 2048 using 64-bit integers. The Julia code uses a further optimization that requires addressing memory efficiently by bit-packed bytes to get a further speed-up of a factor of two which wouldn't appear to be possible in Phix (or at least not efficiently). Good luck on this!--GordonBGood (talk) 05:15, 17 December 2018 (UTC)