2
\$\begingroup\$

I'm implementing the following function for signed integer numbers: given endpoints of a closed interval lo and hi, and inputs x (in [lo..hi]) and dx, I'd like to compute the "reflected sum": if x + dx is still in [lo..hi] then that's it; otherwise the underhanging or overhanging portion is "folded back" onto the result (shown as y below). Basically, x is "bouncing around" in the interval.

                             overhang
                             /--\
                     dx
                 -------------->
--------[-------|-------|---]---|------
       lo       x       y   hi  x + dx
                        <--- 

Because this is for a hardware circuit, I am doing this using Clash's sized Signed integer type and width-extending addition, otherwise it is normal Haskell code.

My current implementation is the following:

bounce :: (KnownNat n, KnownNat k, (k + 1) <= n) => (Signed n, Signed n) -> Signed n -> Signed k -> (Signed n, Bool)
bounce (lo, hi) x dx
    | under > 0 = (lo + under, True)
    | over > 0 = (hi - over, True)
    | otherwise = (resize new, False)
  where
    new = add x dx
    under = resize $ resize lo - new
    over = resize $ new - resize hi

Things I don't like about this implementation:

  • There is a lot of noise about bit widths (all the resize calls)
  • Overall, it is not immediately obvious by just looking at the code what it does. It feels like it's doing a lot of seemingly ad-hoc arithmetic operations that "just happen" to work.

I am looking for improvements that come from the structure of the problem, not "oh you should rename x to theNumberThatIsBouncingAround because one-letter variable names bad".

\$\endgroup\$
1
\$\begingroup\$

I don't think your code agrees with your spec: Your code looks like it can only implement a function built from three line segments.

You shouldn't need explicit resize.

bounce (lo, hi) x dx = let
  (bounces, remainder) = divMod (add dx $ x-lo) $ hi-lo
  in (if even bounces then lo + remainder else hi - remainder
     ,bounces /= 0)
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Unfortunately, divMod by a non-power-of-two is not really implementable as a combinational circuit. \$\endgroup\$ – Cactus Feb 1 at 0:45
  • \$\begingroup\$ I'm happy with not supporting multiple bounces in one timestep. \$\endgroup\$ – Cactus Feb 1 at 0:46
  • \$\begingroup\$ You are already implementing divMod by means of a lookup table for div in {-1,0,1}. That's why your code looks improvable to you. You do in fact need to implement divMod in some way, for that is your problem statement. \$\endgroup\$ – Gurkenglas Feb 1 at 0:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.