Join devRant
Do all the things like
++ or -- rants, post your own rants, comment on others' rants and build your customized dev avatar
Sign Up
Pipeless API
From the creators of devRant, Pipeless lets you power real-time personalized recommendations and activity feeds using a simple API
Learn More
-
POSTMORTEM
"4096 bit ~ 96 hours is what he said.
IDK why, but when he took the challenge, he posted that it'd take 36 hours"
As @cbsa wrote, and nitwhiz wrote "but the statement was that op's i3 did it in 11 hours. So there must be a result already, which can be verified?"
I added time because I was in the middle of a port involving ArbFloat so I could get arbitrary precision. I had a crude desmos graph doing projections on what I'd already factored in order to get an idea of how long it'd take to do larger
bit lengths
@p100sch speculated on the walked back time, and overstating the rig capabilities. Instead I spent a lot of time trying to get it 'just-so'.
Worse, because I had to resort to "Decimal" in python (and am currently experimenting with the same in Julia), both of which are immutable types, the GC was taking > 25% of the cpu time.
Performancewise, the numbers I cited in the actual thread, as of this time:
largest product factored was 32bit, 1855526741 * 2163967087, took 1116.111s in python.
Julia build used a slightly different method, & managed to factor a 27 bit number, 103147223 * 88789957 in 20.9s,
but this wasn't typical.
What surprised me was the variability. One bit length could take 100s or a couple thousand seconds even, and a product that was 1-2 bits longer could return a result in under a minute, sometimes in seconds.
This started cropping up, ironically, right after I posted the thread, whats a man to do?
So I started trying a bunch of things, some of which worked. Shameless as I am, I accepted the challenge. Things weren't perfect but it was going well enough. At that point I hadn't slept in 30~ hours so when I thought I had it I let it run and went to bed. 5 AM comes, I check the program. Still calculating, and way overshot. Fuuuuuuccc...
So here we are now and it's say to safe the worlds not gonna burn if I explain it seeing as it doesn't work, or at least only some of the time.
Others people, much smarter than me, mentioned it may be a means of finding more secure pairs, and maybe so, I'm not familiar enough to know.
For everyone that followed, commented, those who contributed, even the doubters who kept a sanity check on this without whom this would have been an even bigger embarassement, and the people with their pins and tactical dots, thanks.
So here it is.
A few assumptions first.
Assuming p = the product,
a = some prime,
b = another prime,
and r = a/b (where a is smaller than b)
w = 1/sqrt(p)
(also experimented with w = 1/sqrt(p)*2 but I kept overshooting my a very small margin)
x = a/p
y = b/p
1. for every two numbers, there is a ratio (r) that you can search for among the decimals, starting at 1.0, counting down. You can use this to find the original factors e.x. p*r=n, p/n=m (assuming the product has only two factors), instead of having to do a sieve.
2. You don't need the first number you find to be the precise value of a factor (we're doing floating point math), a large subset of decimal values for the value of a or b will naturally 'fall' into the value of a (or b) + some fractional number, which is lost. Some of you will object, "But if thats wrong, your result will be wrong!" but hear me out.
3. You round for the first factor 'found', and from there, you take the result and do p/a to get b. If 'a' is actually a factor of p, then mod(b, 1) == 0, and then naturally, a*b SHOULD equal p.
If not, you throw out both numbers, rinse and repeat.
Now I knew this this could be faster. Realized the finer the representation, the less important the fractional digits further right in the number were, it was just a matter of how much precision I could AFFORD to lose and still get an accurate result for r*p=a.
Fast forward, lot of experimentation, was hitting a lot of worst case time complexities, where the most significant digits had a bunch of zeroes in front of them so starting at 1.0 was a no go in many situations. Started looking and realized
I didn't NEED the ratio of a/b, I just needed the ratio of a to p.
Intuitively it made sense, but starting at 1.0 was blowing up the calculation time, and this made it so much worse.
I realized if I could start at r=1/sqrt(p) instead, and that because of certain properties, the fractional result of this, r, would ALWAYS be 1. close to one of the factors fractional value of n/p, and 2. it looked like it was guaranteed that r=1/sqrt(p) would ALWAYS be less than at least one of the primes, putting a bound on worst case.
The final result in executable pseudo code (python lol) looks something like the above variables plus
while w >= 0.0:
if (p / round(w*p)) % 1 == 0:
x = round(w*p)
y = p / round(w*p)
if x*y == p:
print("factors found!")
print(x)
print(y)
break
w = w + i
Still working but if anyone sees obvious problems I'd LOVE to hear about it.38 -
The most important skill you can have is doing things without shame.
Shamelessly stay in your bed all weekends watching PewDiePie, never brushing your teeth, eating Doritos from under your pillow and peeing into empty Mountain Dew bottle if you feel like doing it.
Shamelessly spend your vacation sitting in the toilet with a laptop browsing reddit.
Shamelessly cut your product in half and ship it if you don't feel like perfecting it.
Shamelessly admit that you don't know something when you messed something up at work.
If you are a millennial like me, chances are your gen x parents told you that you have to be perfect / really good to succeed and to be worthy.
You know what? Fuck your parents then. Fuck my parents as well. Admitting this behavior wrong and actually giving up on living like something is always watching is the best thing you can do to your mental health.
I'm lazy. I write "any" here and there when they force me to do typescript at work. When I need a sidebar, I go and copy-paste that jquery snippet. I write like one article a month at best and I really want to say "fuck it" if I just don't feel like it.
You can always give up on everything and it's perfectly fine. This doesn't make you any kind of looser or something. You're perfectly fine.
Too bad I'm only beginning to master that.9 -
This is a public service announcement with a threat at the end of it:
"Do not, I repeat, do NOT attempt to write web applications, or any particular sort of application that works with a relational database (damn near more than half of applications) without a PROPER grasp and knowledge of SQL.
I do not want to see you reaching out for an ORM either, no, you need to learn to properly design a database or to properly interact with them AT most before you even attempt using an ORM OR designing an application from the beginning, shit will only hurt you in the long term I promise, learning SQL can go a looooong fucking way and most DBA's I know make way tf more than people think they make, it might even be an interesting career choice"
If you do not follow the above advise, and I see your ass reaching for building a web application without the above knowledge I will be under your bed at night, putting oil in my hairy body before I jump into bed to you and leave you confused for the rest of your life.
Build to learn, YES, but for the love of Chamberlain and Boyce PLEASE do not neglect SQL. I have seen such neglect REACH production and I am currently wishing I had these mfkers close to me.9 -
Today I spent 9 hours trying to resolve an issue with .net core integration testing a project with soap services created using a third party soap library since .net core doesn't support soap anymore. And WCF is before my time.
The tests run in-process so that we can override services like the database, file storage, basically io settings but not code.
This morning I write the first test by creating a connected service reference to generate a service client. That way I don't need to worry about generating soap messages and keeping them in sync with the code.
I sent my first request and... Can't find endpoint.
3 hours later I learn via fiddler that a real request is being made. It's not using the virtual in-process server and http client, it's sending an actual network request that fiddler picks up, and of course that needs a real server accepting requests... Which I don't have.
So I start on MSDN. Please God help me. Nope. Nothing. Makes sense since soap is dead on .net core.
Now what? Nothing on the internet because above. Nothing in the third party soap library. Nothing. At this point I question of I have hit my wall as a developer.
Another 4 hours later I have reverse engineered the Microsoft code on GitHub and figured out that I am fucked. It's so hard to understand.
2 more hours later I have figured out a solution. It's pure filth..I hide it away in another tooling project and move all the filth to internal classes :D the equivalent of tidying your room as a kid by shoving it all under the bed. But fuck it.
My soap tests now use the correct http client with the virtual server. I am a magician.4 -
While investigating alternatives for translating a query string to a dotnet expression I discovered that roslyn has runtime eval of string as verbatim code.
I had no idea a feature could make me this uncomfortable. It's like discovering an armed bomb under your bed that's "there if you want - it has its uses, just be careful".
At least you have to explicitly reference a package for it. Promise to kill me if I ever am tempted by it. -
So, Our company called us back to office after 8 month.. and reason was our boss is giving.. You guys may be work on bed.. It is bad for your back.. Here we will provide you better working enviornment and please do carry your laptop to office :P
But I think its okay to work from office.. Once I was excited to work from home. But dude you can learn from the person sitting next to you, discuss things around,, can see what others are doing.. Its a progress. At home you are just u and laptop :)
Personally I think its better to work under someone superior obvious he/she should be technical and egoless.. then its more fun.3
Top Tags
Weekly Rant
View