Back to search

University of North Texas

Arithmetic Computations and Memory Management Using a Binary Tree Encoding af Natural Numbers

Abstract

dc:description

Two applications of a binary tree data type based on a simple pairing function (a bijection between natural numbers and pairs of natural numbers) are explored. First, the tree is used to encode natural numbers, and algorithms that perform basic arithmetic computations are presented along with formal proofs of their correctness. Second, using this "canonical" representation as a base type, algorithms for encoding and decoding additional isomorphic data types of other mathematical constructs (sets, sequences, etc.) are also developed. An experimental application to a memory management system is constructed and explored using these isomorphic types. A practical analysis of this system's runtime complexity and space savings are provided, along with a proof of concept framework for both applications of the binary tree type, in the Java programming language.

Degree

thesis:*
Grantor dc:publisher
University of North Texas
Year dc:date
2011

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Haraburda, David
Contributors dc:contributor
  • Tarau, Paul
  • Mihalcea, Rada, 1974-
  • Buckles, Bill

Subjects

dc:subject × 5

Rights

dc:rights
Statement dc:rights
  • Public
  • Haraburda, David
  • Copyright
  • Copyright is held by the author, unless otherwise noted. All rights Reserved.
Language dc:language
English

Identifiers

dc:identifier.*
Identifier
oclc: 817916588
https://digital.library.unt.edu/ark:/67531/metadc103323/
ark: ark:/67531/metadc103323

Chain of custody

source
Harvested from
University of North Texas
Base URL
digital.library.unt.edu/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Haraburda, David. Arithmetic Computations and Memory Management Using a Binary Tree Encoding af Natural Numbers. University of North Texas, 2011. https://doi.org/10.12794/metadc103323