[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)