I’ll have it converted and post the fork
You know, all is good. I got to experience the power of AI and have some good experience with Julia. The Primes development team is making good progress in incorporating a quadratic sieve into the Primes package. I got to experience the good feeling of sharing even if it was short lived. If the author ever responds to my request and offers a license that allows sharing, I might revisit. If not, I will not have any trouble finding other code to work on.
If you want to help on the Primes.jl quadratic sieve, I’d love help.
Here’s the PR. You’ll need more than a single grano salis.
Help me understand. What are the next steps?
Clone the repo and cd into julia directory.
julia --project=.
help?> FlintQS
search: FlintQS flintqs
FlintQS
Julia port of William Hart's FlintQS: a self-initializing quadratic sieve with single large-prime merging and Block Lanczos linear algebra.
Exports flintqs (full prime factorization) and siqs_split (one divisor of a ≥ 40-digit composite).
help?> flintqs
search: flintqs FlintQS
flintqs(n; rng, verbose) -> Vector{BigInt}
Prime factorization of n ≥ 1 as a sorted vector with multiplicity ([] for n == 1). Strips factors below 1000, reduces perfect powers, and splits
the rest with Pollard rho (≤ 18 digits) or the self-initializing quadratic sieve.
help?> siqs_split
search: siqs_split Base.shell_split rsplit split eachsplit sincospi eachrsplit
siqs_split(n; rng, verbose, accept) -> BigInt
Return a nontrivial divisor of the composite n using the self-initializing quadratic sieve. n must have at least 40 decimal digits, no prime
factor below 1000 and not be a perfect power. accept(d) filters which divisors may be returned (default: any); the search continues through the
remaining dependencies, and further sieving, until one is accepted.
include("bench/bench.jl")
| digits | seconds | peak RSS (MB) |
|:--:|:--:|:--:|
| 40 | 0.08 | 401.0 |
| 45 | 0.24 | 416.0 |
| 50 | 0.63 | 475.0 |
| 55 | 1.17 | 556.0 |
| 60 | 3.21 | 842.0 |
That pretty much it.
I had no idea that the port was as complete and really did not expect it to be this good, so soon. You really are good at AI conversion. I am doing some performance testing currently. Here is what I have so far:
10 digits 0.0002589 sec
20 digits 0.11 sec
30 digits 0.11 sec
40 digits 0.11 sec
50 digits 0.35 sec
60 digits 4.4 sec
70 digits 47.7 sec
75 digits 1 min 52 sec
80 digits 4 min 49 sec
90 digits 44 min 52 sec
I am currently trying RSA-100, will take a while. Looks like the larger the number the more performant this routine is.
It has factored every number I have given it so far. Memory has been stable every run, about 1.5 - 3.5G or so.
I was a little confused on how it handled the numbers between the Pollard Rho cutoff and 40 digits. It sounded like they might not be processed. But it is more clear now that they are processed through the sieve using 40 digit parameters and the timing is almost flat. Very curious.
I turned on verbose output and it raises a question. There are columns for full, combined, partials and target. I assume these are number of relations found. But it is not clear how full, combined and partials are related to target. I could not see a relationship at the point the algorithm factored. You would think that it would be one of the numbers or a sum of two or something like that but I could not see a pattern.
Interesting questions, but remember the NaCl? My being good at conversion amounts to sitting in the captain’s chair on the deck of the Enterprise and saying Make it so, Mr. Sulu. I gave it the github address with instructions to fork and implement in Julia. There was some truly minor back and forth but really very little glory to be claimed. After all, I dropped out of FORTRAN in 1965 when I tried to do the all the ways to make change for a dollar recursively.
I have been programming for over 50 years. Decades with Fortran, C, and assembly using almost every supercomputer, mainframe, and minicomputer made. Heavily invested with Python in retirement. Only spent a short time learning Julia. However, I can’t do what you did in a day in months. I have looked at converting FlintQS several times and after some few hours my brain blew up. It is pointer hell, pointer to pointers all over the place. No doubt fast and efficient, but very hard to follow and near impossible to convert by hand. I probably could if I took months to do it. The issues I noted are small and should be easy fixes. I will spend a few days going over the code and recommend changes.
BUT I DIDN’T DO IT BY HAND! I just murmured an incantation and scattered tokens. No human neurons were sacrificed in the effort.
I don’t have your depth of experience in programming so whenever I do, I go out of my way to keep things simple because, as Brian Kernighan says “everyone knows that it twice as hard to debug as it is to program it in the first place, and so if you make it as clever as possible you’ll never be able to debug it.” In fact, it was when I got to pointers in K&R that I turned my attention to learning bash and all the beautiful little gems in the CLI. That gave me a leg up on Perl, which gave me a leg up on Python and R (which I took up at the same time, along with leveraging dim memories of dBase II to combined with SQL). I tried Haskell and liked it quite a bit except I could never get my head around monads so you could actually do, you know, like I/O? I tried C++ and fled in horror; it tries so hard to keep you from shooting yourself in the foot that it won’t let you actually use it. Go seemed promising but I couldn’t really see the advantages over C. I dabbled in Rust without much enjoyment.
And then I decided to try Julia. What a pleasure! Package management is a first class feature. Strong typing is encouraged but not mandatory. All-in-all it has superior ergonomics.
Strong typing is not encouraged for function signatures, only for structs. And even in structs you might need unions. For automated differentiation you always need duals, and if you strongly type anything they won’t work.
Don’t underestimate what you have done. Julia is a young but promising language. With every new language there is the problem of the language being good but missing the libraries and packages of other languages that have been around for decades. AI can close that gap quickly. Find a package in another language that does what is needed, just convert it (if licensing does not get in the way) and spend some time documenting and polishing. Or have AI generate the new package based on requirements. I have read opinions that AI code hurts because over time developers will lose skills and lose domain knowledge. Time will tell but this sure looks like a revolutionary event.
I dabbled in Rust for a few months. I felt I was fighting the compiler more than coding. The built applications are fast for sure. I like to work with big integers and floats. Rust has a package called rug that interfaces with gmplib. Rug has an issues that limits the size of the arbitrary precision values. That is what encouraged me to look at Julia.
I tried Go language but I found it to be the least performant language for working with big integers and floats. Julia is much better.
Python has a great big integer and float package (gmpy2), very comprehensive. If you are developing code that is working with millions or billions of digits (computing pi for instance) it is great. However working with millions of smaller values, like you do with prime factoring, Python is not performant, Julia wins.
I’m drawn to strong typing because it helps me keep things straight. Thankfully, I no longer have to differentiate, which is a good thing considering how poorly I did in calc.
Since this got derailed already, I’ll ask: I understand we want generic methods since they are composable. But I guess we also want specialized methods. Otherwise, what’s the point of having multiple dispatch? Or is it a feature of tue language that should not be used in everyday coding?