Evaluating Monotonic Functions using Binary Search

This work addresses the accurate (correctly rounded) evaluation of arbitrary functions. The simplest solution is to use a Look-Up Table (LUT), with a storage requirement (hence area) that grows linearly with the output word size, but exponentially with the input word size. This limits its applicability to small input word sizes. For monotonic functions, a binary search in the output domain enables implementations whose area scales linearly with the input word size and exponentially with the output word size. This article introduces several novel architectures exploiting this idea, investigates their efficient mapping to FPGA micro-architecture using features such as \(k\) -input LUT and fast carry logic, compares them to the LUT approach in area and delay, and demonstrates an application to a Gaussian pseudo-random number generator.