Author Topic: Algorithms Quiz (anyone can give it a shot, please!)  (Read 6595 times)

0 Members and 1 Guest are viewing this topic.

Offline The E

  • He's Ebeneezer Goode
  • Global Moderator
  • 213
  • Nothing personal, just tech support.
    • Steam
    • Twitter
Re: Algorithms Quiz (anyone can give it a shot, please!)
Ah, but remember this post:
#3 was changed to 250 million 200 character strings, apparently the point was that loading all of it into memory wouldn't be feasible.  We did get some solutions, a lot of brute force attempts but one guy in particular had some very interesting solutions for most of the problems.

I am not quite certain what cutting the problem up into discrete packages gives you, aside from the risk of never finding your duplicate.

Under the altered conditions, some measure must be taken to reduce memory usage. Portej's solution requires, in a pessimistic case, 9.87*10^282 bytes of memory, if not more due to oerhead. This is at best impractical.

I would really like to see the winning solution, though.
Let there be light
Let there be moon
Let there be stars and let there be you
Let there be monsters and let there be pain
Let us begin to feel again
--Devin Townsend, Genesis

 

Offline chief1983

  • Still lacks a custom title
  • 212
  • ⬇️⬆️⬅️⬅️🅰➡️⬇️
    • Minecraft
    • Skype
    • Steam
    • Twitter
    • Fate of the Galaxy
Re: Algorithms Quiz (anyone can give it a shot, please!)
Turns out the winning one might not have been optimal, however it was one of the best approaches to solving it with an algorithm that we saw.  I'll post the PDF from my laptop tomorrow probably.

Also, storing primes for cracking security would essentially be making a primes rainbow table.  Sure it's massive but it's what rainbow tables are all about.
Fate of the Galaxy - Now Hiring!  Apply within | Diaspora | SCP Home | Collada Importer for PCS2
Karajorma's 'How to report bugs' | Mantis
#freespace | #scp-swc | #diaspora | #SCP | #hard-light on EsperNet

"You may not sell or otherwise commercially exploit the source or things you created based on the source." -- Excerpt from FSO license, for reference

Nuclear1:  Jesus Christ zack you're a little too hamyurger for HLP right now...
iamzack:  i dont have hamynerge i just want ptatoc hips D:
redsniper:  Platonic hips?!
iamzack:  lays

 

Offline Spicious

  • Master Chief John-158
  • 210
Re: Algorithms Quiz (anyone can give it a shot, please!)
Also, storing primes for cracking security would essentially be making a primes rainbow table.  Sure it's massive but it's what rainbow tables are all about.
It's just say a few hundred orders of magnitude bigger.

You could always partition the words by starting letter, distribute each somewhere and repeat on subsequent letters until lists are small enough to work with in memory. Sounds like it could work nicely with a language like Erlang or Go.

 

Offline Bobboau

  • Just a MODern kinda guy
    Just MODerately cool
    And MODest too
  • 213
Re: Algorithms Quiz (anyone can give it a shot, please!)
I have a hard drive that can hold one trillion bytes of information, that should get me at least a decent sized list of primes. remember I don't need all primes up to N to factor N, I just need all primes up to sqrt(N), if I have a huge list of primes in a file on my hard drive, I just load one prime try to divide N with it and then move on until I find one that divides evenly.
Bobboau, bringing you products that work... in theory
learn to use PCS
creator of the ProXimus Procedural Texture and Effect Generator
My latest build of PCS2, get it while it's hot!
PCS 2.0.3


DEUTERONOMY 22:11
Thou shalt not wear a garment of diverse sorts, [as] of woollen and linen together

 

Offline castor

  • 29
    • http://www.ffighters.co.uk./home/
Re: Algorithms Quiz (anyone can give it a shot, please!)
I am not quite certain what cutting the problem up into discrete packages gives you, aside from the risk of never finding your duplicate.
The point is that if there is a cheap way to tell which of the strings can't be duplicates in any case, we don't have to spend time comparing them against each other (other assumed benefits are the possibility for parallel processing and better cache utilization due to smaller working set). I admit it's not that easy in practice, since managing the memory usage would be quite tough even with the original setting. And if the input would need to be split to separate physical files it'd get slow as hell.  

edit: I quess you could also use an incremental version of the sorting idea; read the first n characters of every string, along with their offsets in the file. Sort, throw away unique lines. Append the next n characters to the remaining strings, sort again, discard unique strings. And so on..
« Last Edit: February 11, 2010, 12:34:45 pm by castor »

 

Offline Spicious

  • Master Chief John-158
  • 210
Re: Algorithms Quiz (anyone can give it a shot, please!)
I have a hard drive that can hold one trillion bytes of information, that should get me at least a decent sized list of primes. remember I don't need all primes up to N to factor N, I just need all primes up to sqrt(N), if I have a huge list of primes in a file on my hard drive, I just load one prime try to divide N with it and then move on until I find one that divides evenly.
Keep in mind that for RSA these primes would be on the order of at least 2^512, if not 2^2048. Now, the number of primes less than n is ~n/log n - numbers that make a trillion puny by comparison.

 

Offline Bobboau

  • Just a MODern kinda guy
    Just MODerately cool
    And MODest too
  • 213
Re: Algorithms Quiz (anyone can give it a shot, please!)
well lets see here a 2^512 number would need, somewhere round 1.5*10^75 primes. so, yeah I guess your right.
Bobboau, bringing you products that work... in theory
learn to use PCS
creator of the ProXimus Procedural Texture and Effect Generator
My latest build of PCS2, get it while it's hot!
PCS 2.0.3


DEUTERONOMY 22:11
Thou shalt not wear a garment of diverse sorts, [as] of woollen and linen together

 

Offline CP5670

  • Dr. Evil
  • Global Moderator
  • 212
  • 142857
Re: Algorithms Quiz (anyone can give it a shot, please!)
There is no efficient way to do problem 1 for huge numbers. It amounts to computing prime gaps, and as far as I know the only ways to do that are essentially brute force checks as people brought up earlier. There are some results giving bounds on prime gaps or describing them asymptotically, so you could use them to get a starting estimate or to eliminate some choices, but they are not sharp at all.

If you just want to find large primes, then that's comparatively easier.