Do all the things like ++ or -- rants, post your own rants, comment on others' rants and build your customized dev avatarSign Up
From the creators of devRant, Pipeless lets you power real-time personalized recommendations and activity feeds using a simple APILearn More
It's so trivial it *shouldn't* work, but it does.
Ranchonyx10019361dSooo... I will prolly dl it. But what then?
Floor() and ceil() on a cpu?
Putting this on a gpu would be better.
ChristoPy1597361dI don't get a single word
@Ranchonyx manually call the script, with any positive factors a and b.
If it says it found an Ns (a number swap) it means theres at least one trivial transformation that leads to fast factorization of the product.
The format is
So if your product is 986, the first number this system tries is
Although I only tested it for products with two unique nontrivial factors, up to the 997th prime, or all the products under one million.
This just finds I ans J combinations that work.
For the actual factoring we do the same substitutions, and attempt to generate chains of trivial factors for each iteration of IJ.
If we found a combination that works, then the last factor in any given chain, will be one of the actual factors of our product.
Anyway did it run? And did it work at all for you?
@-ANGRY-STUDENT- I barely got decimal to work and still havent added that to the script to do larger numbers.
You are more than welcome to translate it. All it does is text swapping and iteration.
Should be trivial for a shader.
But actually you bring up something interesting. Was looking at conways constant, which gives the next number in a look-and-say sequence. And I thought, what if factorization isnt a factoring problem, but simply a text transformation problem?
You can actually look at the problem as run length encoding a "image" made of a "palette" of factors.
Each factor, 2, 3, 5, etc, becomes a color.
On a standard "image" (an untransformed product), the palette space of possible colors is huge.
This transforms the product from a large color space to a smaller one, composed of, at most five or six factors from what I've seen.
(Although when I write the actual factorizer, I'll collate the list of all trivial factors in the factor trees).
And because this is possible, we can actually precompute a list of bases that are the product of a combination of these trivial factors. And what that will enable you to do is change the product to another number that is of this special base, and consequently transform the factorization from a division problem into a simpler problem, as outlined in an earlier post.
Basically, you know those rules for quick division? "If it ends in 0 its divisible by 2 and five?"
You can actually derive those rules yourself using a certain change of base formula. So for every product we might try, we dont need to know the rules for every possible factor beneath it..
We only need to know the rules for determining if a product is a multiple of
2*2, 2*3, 2*3*5.. etc
Also from what I saw, the factor chain was always smooth, i.e. just one example, if 2 and 5 were present, 3 would always be present. So that reduces what we have to look for.
Wouldnt even have considered this before had you not commented.
iSwimInTheC41885360dWhat is the use case for this?
Wisecrack7229360d@iSwimInTheC faster bruteforcing.
Thats about it.
It varys considerably in timing but the bulk of numbers return pretty quickly. The second largest set of numbers return in about half the time it would take to bruteforce the lowest factor.
If this works its plausible theres other product transformations that are more efficient, or algorithms to better determine the variables I and J.
Lets say varying *any* two digits in a product works (instead of the middle and unit digit in the template), but the set of possible solutions is some percentage of the lowest factor of p (with a nontrivial factor A).
So searching each ends up being depth first.
But if we search *across* the digits at a shallow depth, some are bound to return an answer faster than others.
Thats just one example though.