[HN Gopher] Project Euler on a Microcontroller
       ___________________________________________________________________
        
       Project Euler on a Microcontroller
        
       Author : shawnnapora
       Score  : 61 points
       Date   : 2022-07-29 18:31 UTC (4 hours ago)
        
 (HTM) web link (shawnnapora.github.io)
 (TXT) w3m dump (shawnnapora.github.io)
        
       | Evidlo wrote:
       | Alternatively you could compile to/write for a virtual machine.
        
         | shawnnapora wrote:
         | A virtual machine is interesting to me when it corresponds to a
         | hardware target, since then that isn't hiding complexity in
         | software. I suppose, though, that an enterprising individual
         | could make a custom hardware target that implements an overly
         | complex, overspecific instruction set and win at hardware golf
         | but I'd honestly be very impressed.
         | 
         | The positive part about virtual machines in general would be
         | the ease of debugging and sharing/validating answers, though.
        
       | bjourne wrote:
       | Pretty cool. Maybe there are some pop count/bit-twiddling tricks
       | for checking divisibility with constants? Like this:
       | https://stackoverflow.com/a/39386483/189247
        
         | Jtsummers wrote:
         | The program bypasses the need to actually check the particular
         | number against 3 and 5 using any kind of arithmetic
         | instructions, instead it's keeping separate values for 3-count
         | and 5-count which will be either 3 or 5 when the number is a
         | multiple of either. It then performs a clear on it. So it has
         | this state when it gets to the checks:                 n
         | 3-count   5-count       1    1         1       2    2         2
         | 3    3         3       4    1         4       ...
         | 
         | So the check is just a _cpi_ (compare immediate) instruction
         | for whether the particular counter is 3 or 5. Which is probably
         | faster than bit twiddling, especially since they don 't have a
         | pop count instruction available in the instruction set. On an
         | instruction set with that, I imagine it would be a useful trick
         | though.
        
           | bjourne wrote:
           | The point of bit-twiddling is to produce a number n that is 1
           | or -1 if counter is divisible by 3 or 5 and 0 otherwise, and
           | then add either mul(n, counter) or and(n, counter) to the
           | result. It avoids branches which could shave off a few bytes
           | depending on how branch instructions are encoded. Since we're
           | golfing, we're not interested in speed, only program size.
        
             | Jtsummers wrote:
             | Still not an option on the platform in the article, though.
             | You'd have to make your own pop count and implement it
             | likely with a loop and bit shifting. It's almost certainly
             | going to take more instructions than this and end up with
             | as many branches as a result. The instruction set is very
             | limited. Though quoting myself:
             | 
             | >> On an instruction set with that [pop count], I imagine
             | it would be a useful trick though.
        
       | dmitrygr wrote:
       | 134 bytes is a lot
        
         | shawnnapora wrote:
         | A lot relative to _what_? :) These 134 bytes will emit an
         | answer without requiring a kernel or a runtime, either of which
         | generally will be orders of magnitude larger than 134 bytes
         | alone.
        
           | dmitrygr wrote:
           | i do a lot of uC work, i meant that for this task on that uC,
           | it is a lot of bytes, less than half that many can easily
           | accomplish this task. possibly less, if i could be bothered
           | to spend time
        
           | dmonitor wrote:
           | If we keep down this path, we will some day have a code-golf
           | optimized CPU architecture.
           | 
           | Used transistor count as the blog suggests is clearly the
           | best metric
        
       | softbuilder wrote:
       | I am reminded of Txtzyme:
       | https://github.com/WardCunningham/Txtzyme
        
       | victor82 wrote:
       | You can avoid using abstractions and write it directly on the
       | silicon, it's not really difficult, it turns into a bunch of
       | muxes, registers and adders (as shown in the link below) and
       | solves the problem in just 333 clock cycles, using a minimum of
       | power
       | 
       | https://gist.github.com/vmunoz82/49de4c63bee1768283162ec5406...
       | class Euler(Elaboratable):         def __init__(self):
       | self.output = Signal(19)              def elaborate(self,
       | platform):             m = Module()                  count5 =
       | Signal(3)             c3, c5 = Signal(17), Signal(18)
       | cond3, cond5 = (c3 < 1000) & (count5 != 0), (c5 < 1000) & (count5
       | < 3)                  m.d.sync += count5.eq(Mux(count5 == 4, 0,
       | count5+1))             m.d.sync += [                 c3.eq(c3+3),
       | c5.eq(Mux(cond5, c5+5, c5))             ]             m.d.sync +=
       | self.output.eq(self.output +
       | Mux(cond3, c3, 0)+Mux(cond5, c5, 0))             return m
        
       | Prcmaker wrote:
       | I learned real Matlab using project Euler in my first year of
       | uni. I'd been taught it previously as 'just a calculator', but
       | working through the problems opened up a world of skills I knew
       | nothing about. Those learnings pushed me in to microcontrollers
       | and got me thinking outside the box in a way I still use
       | regularly. I can't recommend it highly enough.
        
       ___________________________________________________________________
       (page generated 2022-07-29 23:00 UTC)