The Origin of the Binary-Search Paradigm,

Abstract

In a binary-search algorithm for the computation of a numerical function, the interval in which the desired output is sought is divided in half at each iteration. The paper considers how such algorithms might be derived from their specifications by an automatic program-synthesis system. The derivation of the binary-search concept has been found to be surprisingly straightforward. The programs obtained, though reasonably simple and efficient, are quite different from those that would have been constructed by informal means. Additional keywords: Mathematical programming, Specifications, Transformations(Mathematics), and Derivatives(Mathematics). (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Mar 01, 1985
Accession Number
ADA154367

Entities

People

  • R. Waldinger
  • Z. Manna

Organizations

  • Stanford University

Tags

Communities of Interest

  • C4I

DTIC Thesaurus Topics

  • Air Force
  • Algorithms
  • Computations
  • Computer Programming
  • Computer Science
  • Computers
  • Intervals
  • Iterations
  • Language
  • Number Theory
  • Numbers
  • Real Numbers
  • Side Effects
  • Specifications
  • Square Roots
  • Standards

Readers

  • Operations Research
  • Software Engineering.