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

PDF Version Also Available for Download.

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 ... continued below

Creation Information

Haraburda, David December 2011.

Context

This thesis is part of the collection entitled: UNT Theses and Dissertations and was provided by UNT Libraries to Digital Library, a digital repository hosted by the UNT Libraries. It has been viewed 667 times , with 11 in the last month . More information about this thesis can be viewed below.

Who

People and organizations associated with either the creation of this thesis or its content.

Chair

Committee Members

Publisher

Rights Holder

For guidance see Citations, Rights, Re-Use.

  • Haraburda, David

Provided By

UNT Libraries

With locations on the Denton campus of the University of North Texas and one in Dallas, UNT Libraries serves the school and the community by providing access to physical and online collections; The Portal to Texas History and UNT Digital Libraries; academic research, and much, much more.

Contact Us

What

Descriptive information to help identify this thesis. Follow the links below to find similar items on the Digital Library.

Degree Information

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.

Language

Collections

This thesis is part of the following collection of related materials.

UNT Theses and Dissertations

Theses and dissertations represent a wealth of scholarly and artistic content created by masters and doctoral students in the degree-seeking process. Some ETDs in this collection are restricted to use by the UNT community.

What responsibilities do I have when using this thesis?

When

Dates and time periods associated with this thesis.

Creation Date

  • December 2011

Added to The UNT Digital Library

  • Oct. 2, 2012, 4:18 p.m.

Description Last Updated

  • Jan. 21, 2014, 1:41 p.m.

Usage Statistics

When was this thesis last used?

Yesterday: 1
Past 30 days: 11
Total Uses: 667

Interact With This Thesis

Here are some suggestions for what to do next.

Start Reading

PDF Version Also Available for Download.

Citations, Rights, Re-Use

Haraburda, David. Arithmetic Computations and Memory Management Using a Binary Tree Encoding af Natural Numbers, thesis, December 2011; Denton, Texas. (digital.library.unt.edu/ark:/67531/metadc103323/: accessed June 25, 2017), University of North Texas Libraries, Digital Library, digital.library.unt.edu; .