Factor Stencils Review / HowTo
Вставка
- Опубліковано 27 лип 2024
- Factor stencils based on a design from the 1920s by D. N. Lehmer. His will factor any number up to 3,000,000,000,000. Mine are smaller, so only factor up to 200,000.
This is episode 37 of my video series about calculating devices.
Visit my site for PDFs and SVGs to download and make your own, and more detail on how to use them: cstaecker.fairfield.edu/~cstae...
Lehmer seive photo by Marcin Wichary, licensed cc-by.
End song inspired by "Hotter Than a Molotov" by The Coup.
Chris Staecker webarea: cstaecker.fairfield.edu/~cstae...
The complexity of these solving devices really makes you appreciate the brute force computing devices we carry in our pockets. Thanks for the video. Never heard of these devices before.
I came here for the machines and I stayed for the powerful beauty of paper. you are a teaching wizard!
For someone who doesn't have a fancy cutting machine, or a kid, or preschool, maybe you can reverse the empty and filled circles and then print them on transparent plastic sheets?
Powerful beauty indeed. I'm a semi-retired engineer and your videos are exquisite. I wish all those years ago in university that I had had you as a math professor. I not only would I have learnt the science, but also how to appreciate the art.
OMG that Lehmer Sieve is a photo I took at the Computer History Museum!
Nice! Thanks for the photo (and sorry I didn't credit you in the description- I did now). This is the best picture I could find of the mechanism- I've never seen it myself.
Oh, no worries! Here are more that I took of both machines: www.flickr.com/search/?user_id=8399025%40N07&sort=date-taken-desc&text=lehmer&view_all=1
I really appreciate you doing these videos.
This is beautiful and it makes you appreciate our computers even more. I love your channel!
My grandpa was a test engineer in the 60's and i have all of his stencils. He never threw out any of the analog stuff he used. His stencils are pretty standard for the time though, and had various curves and circles. i don't have his slide rule though, which was stolen by a drug dealer. i do have his pocket log book with a leather binding. he didn't have any of the crazier calculators, just the really nice slide rule and the log book. all of his stencils seem to be for charting or drafting. i have some of his old graph sheets too, but they are just standard engineering sheets with green grid on one side and blank on the other with a border of grids.
he was always quick to adopt technology and would often marvel at how crappy vernier calipers and slide rules were compared to calculator IC's lol
Checked on my Arithma and 379×499 is indeed 189121.
Thank you for your great video! It helped inspire me to making my own set (and my own UA-cam video) that goes into detail about the math behind the stencils.
Very cool. Never seen such a device. But can they crack a 1024 bit RSA code? Or a ten terrapins per fornight code? And will they blend?
Man what preschool did you take your kids to??? I wanna go there!
Sweet, amigo. Now I think I might begin to understand that part of Pre-Algebra for Dummies that I'm working way through. Maybe.
. . . Cindy & I were talking this morning about how you manage to show the history, the heart of what many folks consider a heartless subject. Cindy said "Oh, so it's like math for liberal arts majors." At which point it was time to put the breakfast dishes in the machine and separate the tussling cats.
. . . Keep on teaching us stuff, Chris. And stay safe & well, amigo.
Cindy gets it!
Mesmerizing, and hilarious too! Thanks
What a powerful video. Simply beautiful. :'-)
I'm always amazed and in awe of the geniuses who figure this stuff out! How the hell do they do it?
They start with a simple idea - "Can I prime factorize with punch cards?" - and keep layering until they get it to work.
"A journey of one thousand miles begins with a single step."
excellent outro
I might be late and superfluous, but the most CNC paper cutters also accept a pen attachment. I appreciate all your videos.
Yes- my stencils could've been much better if I had access to one of those. I was using the base level Cricut, which is cutting only- no printing.
what an execution.
Paper "computers" are very interesting.
yeah somebody made a series on youtube called "Paper Computers"
So complex, it's hard to imagine this is a shortcut, but I'm sure this was amazing in it's day
How do you know when to stop.... After the first R value there is a list of possibilities, but many interations later you got the answer, in this case there was only two factors
For the very large numbers, which could have many prime factors, would the iterations eventually cycle, or do you have to check by multiplying the potential factors to see if that gives you the value you're trying to prime factorise?
I get the feeling that for six-digit numbers it might not be a shortcut, but maybe for numbers around a trillion it is.
These days, you can just ask Wolfram Alpha to factorize the number. It'll take a couple of seconds at most. But it might well be using Lehmer's work to do it.
Your kids preschool has a laser cutter!!
It’s just a little blade- fancy, but not extravagant.
If you use quadratic residues, can't you try Dixon's factorization method? Well I guess it wasn't invented yet
Fermat would have used his technique to see that 189121+60²=439² and therefore 189121=(439+60)(439-60). The effort required for that is sixty very small additions and knowing the squares of 435 through 439. At this scale at least, Lehmer's algorithm has only theoretical value.
I comment to help statistics
Thanks!
I seem to remember a documentary about station X them showing codebreakers using a very similar system of stencils lining up the holes to crack codes early in the second world war before the more mechanical devices were perfected. Do you know if he’s worked on the similar principle?
I'd be very interested to hear more details about this- I've never heard that this kind of thing was used, but factoring is absolutely key to modern crypto, so it wouldn't surprise me. Do you recall the name of the documentary? thanks-
@@ChrisStaecker sorry I can’t remember the name of the documentary I watched a fair number about Bletchley house over the years.
However talking to my father he remembered that the sheets were called Banbury sheets after the town where they were apparently made which we have a connection to. There appears to be some reference to them finding some of these intact in one of the huts at Bletchley on the web searching for them by name. I’m blind so it takes me a time to do more in-depth searching but perhaps that would be enough for you to do your own research.
@@r0bhumm Thanks so much for this! I now see many pages about Banbury Sheets, and even a wikipedia article "Banburismus" about the specific technique. I will absolutely look into this some more.
(By the way I am interested in how you receive my videos as a blind person- I'm interested in accessibility but I don't know any blind people. I've uploaded subtitles for some videos, but it seems to be that the auto-generated ones are pretty good so I'm not sure it's worth it to spend the time to do by hand. Do you personally appreciate real subtitling, or do you find the auto-generated ones good enough? I'd love to hear any more thoughts you have about accessibility of my videos if you want to share- please feel free to email me. But don't bother if its a hassle- I know it's not your job to educate me on these things- thanks!)
Thks I assume the work to generate the factor stencils is NP but factoring a number with them is linear.
?can the factor stencils be generated & overlayed within a computer instead of cards?
If so, ?has anyone accomplished it?
I'm not aware of this stencils method being used directly in modern factoring algorithms, but I'd guess that it wouldn't be terribly helpful. I think the stencils themselves have been mostly forgotten by time, but the ideas that I outlined are well-known today and regarded as very basic. Modern techniques are beyond my understanding (even as a PhD mathematician!), but I'd say they are certainly more advanced than the stencils.
189121 is apparently close enough to a square that Fermat's factorisation algorithm works quite fast
first find where about square root is
400^2 = 160000, that's 30k too small
30k / (400*2) = about 35
435^2 = 160000+35*400*2+35^2=189225
434^2 = 435^2 - 2*434 + 1 < 189121
so ceil(sqrt(189121))=435
now subtraction
435^2 - 189121 = 104, not a square
436^2 - 189121 = 104 + 2*435 + 1 = 975, 31^2 = 961, 32^2 = 1024, so not a square
437: 975+2*436+1 = 1848, 42^2 = 1764, 43^2 = 1849, not square
438: 1848+874+1=2723, 52^2=2704, not square
439: 2723+876+1=3600 = 60^2
189121 = 439^2 - 60^2 = (439-60)(439+60) = 379*499
isn't that useful for huge numbers, but here it worked
also your website is down again
any chance that, after you fix it, you yourself make wayback machine website (internet archive) go over and save all the pages and documents?
Robinson's stencils look like the format of an IBM punch card.
Yes- they programmed a card-punching machine to make them. The only time I know of that a fancy algorithm was written to produced standard punched cards that would then be used BY HAND by people!
@@ChrisStaecker thought I recognized them. Telling my age, my first program was hand-coded on paper. Then keypunch operators created a stack of cards. I had to visually verify before sending to the card reader for processing by an IBM mainframe.
I've enjoyed your channel. Brought back a lot of memories I've had some of the math gadgets that you shown.
I love the Hello Kitty Calculator.
Sometimes the strongest characters are the ones in the background.
Having these is so far beyong nerdy.
Like, people own nerdy things so they can quickly show off how smart they are. Such as "look, I can use a slide rule and divide 853 by 11"
But this is like "okay, I'll get back to you in 30 minutes"
Men's Hello Kitty Best Dad Father's Day Tee Shirt 👕
In conclusion.
It is magic and wizards exist.
I am sorry you chose to skip the maths.
I'm never going to make and use these cards - if I really need to factor a large number I'll use a computer.
The maths (the "how/why it works") is the most important thing about these cards.
No, the most important thing about them, is they allowed the user to more efficiently find the prime factors of large numbers.
These videos are not really an explanation of the underlying principles of many of the technologies shown.
Like the nomographs or other more complicated to explain topics, the general operation and underlying logic is explained.
But if you want to know why these work or how they were designed, the necessary information is in the video for you to find the further reading you desire.
All of these videos are about outdated, superseded technologies. He is well aware that most people won’t use them. The videos are however about them. They are not an hour + lecture on number theory.
These videos are quite honest about what they are.