18
Wisecrack
73d

Two big moments today:

1. Holy hell, how did I ever get on without a proper debugger? Was debugging some old code by eye (following along and keeping track mentally, of what the variables should be and what each step did). That didn't work because the code isn't intuitive. Tried the print() method, old reliable as it were. Kinda worked but didn't give me enough fine-grain control.

Bit the bullet and installed Wing IDE for python. And bam, it hit me. How did I ever live without step-through, and breakpoints before now?

2. Remember that non-sieve prime generator I wrote a while back? (well maybe some of you do). The one that generated quasi lucas carmichael (QLC) numbers? Well thats what I managed to debug. I figured out why it wasn't working. Last time I released it, I included two core methods, genprimes() and nextPrime(). The first generates a list of primes accurately, up to some n, and only needs a small handful of QLC numbers filtered out after the fact (because the set of primes generated and the set of QLC numbers overlap. Well I think they call it an embedding, as in QLC is included in the series generated by genprimes, but not the converse, but I digress).
nextPrime() was supposed to take any arbitrary n above zero, and accurately return the nearest prime number above the argument. But for some reason when it started, it would return 2,3,5,6...but genprimes() would work fine for some reason.

So genprimes loops over an index, i, and tests it for primality. It begins by entering the loop, and doing "result = gffi(i)".
This calls into something a function that runs four tests on the argument passed to it. I won't go into detail here about what those are because I don't even remember how I came up with them (I'll make a separate post when the code is fully fixed).

If the number fails any of these tests then gffi would just return the value of i that was passed to it, unaltered. Otherwise, if it did pass all of them, it would return i+1.

And once back in genPrimes() we would check if the variable 'result' was greater than the loop index. And if it was, then it was either prime (comparatively plentiful) or a QLC number (comparatively rare)--these two types and no others.

nextPrime() was only taking n, and didn't have this index to compare to, so the prior steps in genprimes were acting as a filter that nextPrime() didn't have, while internally gffi() was returning not only primes, and QLCs, but also plenty of composite numbers.

Now *why* that last step in genPrimes() was filtering out all the composites, idk.

But now that I understand whats going on I can fix it and hypothetically it should be possible to enter a positive n of any size, and without additional primality checks (such as is done with sieves, where you have to check off multiples of n), get the nearest prime numbers. Of course I'm not familiar enough with prime number generation to know if thats an achievement or worthwhile mentioning, so if anyone *is* familiar, and how something like that holds up compared to other linear generators (O(n)?), I'd be interested to hear about it.

I also am working on filtering out the intersection of the sets (QLC numbers), which I'm pretty sure I figured out how to incorporate into the prime generator itself.

I also think it may be possible to generator primes even faster, using the carmichael numbers or related set--or even derive a function that maps one set of upper-and-lower bounds around a semiprime, and map those same bounds to carmichael numbers that act as the upper and lower bound numbers on the factors of a semiprime.

Meanwhile I'm also looking into testing the prime generator on a larger set of numbers (to make sure it doesn't fail at large values of n) and so I'm looking for more computing power if anyone has it on hand, or is willing to test it at sufficiently large bit lengths (512, 1024, etc).

Lastly, the earlier work I posted (linked below), I realized could be applied with ECM to greatly reduce the smallest factor of a large number.
If ECM, being one of the best methods available, only handles 50-60 digit numbers, & your factors are 70+ digits, then being able to transform your semiprime product into another product tree thats non-semiprime, with factors that ARE in range of ECM, and which *does* contain either of the original factors, means products that *were not* formally factorable by ECM, *could* be now.

That wouldn't have been possible though withput enormous help from many others such as hitko who took the time to explain the solution was a form of modular exponentiation, Fast-Nop who contributed on other threads, Voxera who did as well, and support from Scor in particular, and many others.
Thank you all. And more to come.

Links mentioned (because DR wouldn't accept them as they were):
https://pastebin.com/MWechZj9

Comments
  • 4
    @hitko @scor @Voxera @Fast-Nop, @Frederick (because you helped me in the past but fuck if I can remember with what).
  • 5
    "I also think it may be possible to *generator* primes even faster, "

    but alas, *proofreading* is still not possible.

    I guess we'll have colonies on mars before that happens.

    Some things never change.

    also, if I forgot to mention anyone, sorry, you can just throw something at me next time and we'll be even! I'm practically an alzheimer's patient in training, so I won't remember anyway.
  • 2
    Heres the sourcecode for the fixed version of the non-sieve prime generator:

    https://pastebin.com/tgbXYtPU

    run in repl, try 'isPrime(n)'

    Doesn't have to iterate all the numbers before n to tell you primality.

    Still running without fault. I'm currently checking all primes generated by it, under one million, to see if it fails anywhere.

    So far it's working.
  • 3
    I only use a debugger in rare exceptions like memory corruption that causes a malfunction somewhere entirely else. Usually, it's reading the source to find bugs.

    That's good because in my job, I'm working on legacy firmware for devices that are some hundred kilometers away, have no remote access, and that I have never even seen.
  • 1
    @Fast-Nop "I'm working on legacy firmware for devices that are some hundred kilometers away, have no remote access, and that I have never even seen."

    Pardon the vernacular, but your job sounds fucking cool.

    it's all asm or you work in something higher level?

    what kind of devices anyway? (if thats not asking too much).
  • 1
    @Wisecrack It's all in C, only some really low-level parts in assembly. That's bare metal embedded systems, i.e. no operating system, and usually parts of some larger overall systems.

    The cool part is figuring out how sensors and actuators are interfaced, where they are actually located (i.e. what exactly am I even measuring), and taking physics into account. Or sometimes working around seriously misdesigned hardware designs in software.
  • 1
    @Fast-Nop I'm going to assume you work for NASA or build hunter-killer drones from here on out. Don't correct me. It's fun to imagine.

    Closest I ever got to bare metal was programming a simple worm on dos (think it was in nasm, fuck if I remember) and accidentally destroying my computer in the process. Oh and a few instances of blitting to screen over VGA.

    Nothing like you're doing but I can understand the immediate appeal of tinkering at that low a level.

    Are hardware bugs real common?
  • 1
    @Wisecrack Hardware bugs do happen, more on PCB misdesign level than in actual silicon. Or it's changes in the actual device.

    Like, the one I have now changed some heated aluminium tank in favour of stainless steel. Problem is, that conducts heat way worse, so the outer temp sensors are a lot more decoupled from the temps in the vessel, which fucks up the control algo.

    So it's about analysing the physics, coming up with ideas, and changing the software to address that. I have only schematics and pictures, and the testing is done far away by someone else.
  • 0
    sounds very fun to puzzle out.

    you get to run simulations at least? Or is it more like "anticipate as many potential problems as possible, write tests for all of them, and then wait for feedback to determine what the issue is and implement a fix"?
  • 1
    @Wisecrack Simulations?! Haha, you wish. :) No, it's thinking ahead, getting the measurements, and then thinking again what the results mean and how to go ahead from there.
  • 1
    @Fast-Nop "No, it's thinking ahead, getting the measurements, and then thinking again what the results mean and how to go ahead from there."

    You are a bright man and I do not envy the tools you have been given, which apparently amount to coconuts and bamboo.

    Carry on Gilligan. You seem like you're in another world.

    I was gonna insert a reference to iron man here, "something something, next you'll tell me you got kidnapped like an errant weapons-manufacturing billionaire playboy, only to invent power armor using only scrap iron and some common tools" but alas it was too on the nose.

    And this is the story about how my life got flipped, turned upside down.

    You'll have to settle for fresh prince of bel-air references.
  • 1
    Debugging is great.

    Seems like many devs haven't really set it up because a print statements work in a pinch. And sometimes it's daunting if the setup doesn't work out of the box and you need to adjust some weird flag. Then people get used to it and think "I don't need a debugger!"

    I think it's nice to help other team members set up their debuggers and show them how much nicer it is.
Add Comment