Division in logspace-uniform NC¹

¹ EECS Department, University of Wisconsin-Milwaukee, Milwaukee, WI, U.S.A.
² EECS Department, University of Wisconsin-Milwaukee, Milwaukee, WI, U.S.A.; e-mail: This email address is being protected from spambots. You need JavaScript enabled to view it.
³ School of Information Technology, James Cook University, Townsville, Qld. 4811, Australia; e-mail: This email address is being protected from spambots. You need JavaScript enabled to view it.

Received: 25 June 2000
Accepted: 3 August 2001

Abstract

Beame, Cook and Hoover were the first to exhibit a log-depth, polynomial size circuit family for integer division. However, the family was not logspace-uniform. In this paper we describe log-depth, polynomial size, logspace-uniform, i.e., NC¹ circuit family for integer division. In particular, by a well-known result this shows that division is in logspace. We also refine the method of the paper to show that division is in dlogtime-uniform NC¹.