Computer Science – Computational Complexity
Scientific paper
2011-04-15
Computer Science
Computational Complexity
10 pages, 1 figure
Scientific paper
The symbolic representation of a number should be considered as a data structure, and the choice of data structure depends on the arithmetic operations that are to be performed. Numbers are almost universally represented using position based notations based on exponential powers of a base number - usually 10. This representations is computationally efficient for the standard arithmetic operations, but it is not efficient for factorisation. This has led to a common confusion that factorisation is inherently computationally hard. We propose a new representation of the natural numbers based on bags and using the prime successor function as a primitive - prime bags (PBs). This data structure is more efficient for most arithmetic operations, and enables numbers can be efficiently factored. However, it also has the interesting feature that addition appears to be computationally hard. PBs have an interesting alternative interpretation as partitions of numbers represented in the standard way, and this reveals a novel relationship between prime numbers and the partition function. The PB representation can be extended to rational and irrational numbers, and this provides the most direct proof of the irrationality of the square root of 2. I argue that what needs to be ultimately understood is not the peculiar computation complexity properties of the decimal system (e.g. factorisation), but rather what arithmetical operator trade-offs are generally possible.
No associations
LandOfFree
Numbers as Data Structures: The Prime Successor Function as Primitive does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Numbers as Data Structures: The Prime Successor Function as Primitive, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Numbers as Data Structures: The Prime Successor Function as Primitive will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-8941