English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Division is a fundamental problem for arithmetic and algebraic computation. This paper describes Boolean circuits (of bounded fan-in) for integer division (finding reciprocals) that have size &Ogr;(M(n)) and depth &Ogr;(lognlog logn), where M(n) is the size complexity of &Ogr;(logn) depth integer multiplication circuits. Currently, M(n) is known to be &Ogr;(nlogn log,n), but any improvement in this bound that preserves circuit depth will be reflected by a similar improvement in the size complexity of our division algorithm. Previously, no one has been able to derive a division circuit with size &Ogr;(n logc n) for any c, and simultaneous depth less than &OHgr;(log2 n). Our circuits are logspace uniform; that is, they can be constructed by a deterministic Turing machine in space &Ogr;(log n).Our results match the best known depth bounds for logspace uniform circuits, and are optimal in size.The general method of high order iterative formulas is of independent interest as a way of efficiently using parallel processors to solve algebraic problems. In particular, our algorithm implies that any rational function can be evaluated in these complexity bounds.As an introduction to high order iterative methods we also present a circuit for finding polynomial reciprocals (where the coefficients come from an arbitrary ring, and ring operations are unit cost in the circuit) in size &Ogr;(PM (n)) and depth &Ogr;(log n log log n), where PM(n) is the size complexity of optimal depth polynomial multiplication.

Optimal size integer division circuits