Thursday, April 19, 2007

Interval arithmetic

I want to play around with improved overflow check elimination. The Factor compiler already does some elementary overflow check elimination, but is only applicable to counted loops iterating over arrays. I want to generalize this in order to speed up Chris Double's YUV to RGB conversion. YUV to RGB conversion performs a lot of integer additions and multiplications, none of which ever overflow to bignums. If the compiler can infer this fact, then it can replace generic arithmetic with machine arithmetic, resulting in a nice speedup. So as a first step I cooked up an interval arithmetic library, which represents a closed interval as a pair of numbers. I was pleasantly surprised at how simple it was:
: cartesian ( seq1 seq2 -- seq3 )
[ swap [ swap 2array ] map-with ] map-with concat ;

: interval-op ( i1 i2 quot -- i3 )
-rot cartesian [ first2 rot call ] map-with
dup infimum swap supremum 2array ; inline

: >int ( n -- interval ) dup 2array ;

: int+ ( i1 i2 -- i3 ) [ + ] interval-op ;

: int- ( i1 i2 -- i3 ) [ - ] interval-op ;

: int* ( i1 i2 -- i3 ) [ * ] interval-op ;

: int-shift ( i1 n -- i2 ) >int [ shift ] interval-op ;

: int/ ( i1 i2 -- i3 ) [ / ] interval-op ;

: int/i ( i1 i2 -- i3 ) [ /i ] interval-op ;

: int-intersect ( i1 i2 -- i3/f )
[ [ first ] 2apply max ] 2keep [ second ] 2apply min
2dup > [ 2drop f ] [ 2array ] if ;

It is worth noting that the int+ and int- words can be made more efficient:
: int+ ( i1 i2 -- i3 ) v+ ;
: int- ( i1 i2 -- i3 ) reverse v- ;

1 comment:

Daniel Ehrenberg said...

I think you can use an assocs word to make this more clear. This is untested, but I think you could replace

[ first2 rot call ] map-with

with

swap { } assoc>map

HTH

(why won't blogger let me use <pre> tags in a comment?)