P-Adic numbers, basic: Difference between revisions

Content added Content deleted
(New post.)
(New post.)
Line 50: Line 50:
__TOC__
__TOC__



=={{header|C++}}==
This example displays p-adic numbers in standard mathematical format, consisting of a possibly infinite list of digits extending leftwards from the p-adic point.
<syntaxhighlight lang="c++">
#include <cstdint>
#include <iostream>
#include <stdexcept>
#include <string>
#include <vector>

class p_adic {
public:
// Create a p-adic number, with p = 'prime', from the given rational 'numerator' / 'denominator'.
p_adic(uint32_t prime, int32_t numerator, int32_t denominator) : prime(prime) {
if ( denominator == 0 ) {
std::invalid_argument("Denominator cannot be zero");
}

order = 0;

// Process rational zero
if ( numerator == 0 ) {
order = ORDER_MAX;
return;
}

// Remove multiples of 'prime' and adjust the order of the p-adic number accordingly
while ( modulo_prime(numerator) == 0 ) {
numerator /= static_cast<int32_t>(prime);
order += 1;
}

while ( modulo_prime(denominator) == 0 ) {
denominator /= static_cast<int32_t>(prime);
order -= 1;
}

// Standard calculation of p-adic digits
const uint64_t inverse = modulo_inverse(denominator);
while ( digits.size() < PRECISION ) {
const uint32_t digit = modulo_prime(numerator * inverse);
digits.emplace_back(digit);

numerator -= digit * denominator;

if ( numerator == 0 ) {
// All successive digits will be zero, which occurs when the denominator is a power of a prime
pad_with_zeros(digits);
} else {
// The denominator is not a power of a prime
uint32_t count = 0;
while ( modulo_prime(numerator) == 0 ) {
numerator /= static_cast<int32_t>(prime);
count += 1;
}

for ( uint32_t i = count; i > 1; --i ) {
digits.emplace_back(0);
}
}
}
}

// Return the sum of this p-adic number with the given p-adic number.
p_adic add(p_adic other) {
if ( prime != other.prime ) {
std::invalid_argument("Cannot add p-adic's with different primes");
}

std::vector<uint32_t> result;

// Adjust the digits so that the p-adic points are aligned
for ( int32_t i = 0; i < -order + other.order; ++i ) {
other.digits.insert(digits.begin(), 0);
}

for ( int32_t i = 0; i < -other.order + order; ++i ) {
digits.insert(digits.begin(), 0);
}

// Standard digit by digit addition
uint32_t carry = 0;
for ( uint32_t i = 0; i < std::min(digits.size(), other.digits.size()); ++i ) {
const uint32_t sum = digits[i] + other.digits[i] + carry;
const uint32_t remainder = sum % prime;
carry = ( sum >= prime ) ? 1 : 0;
result.emplace_back(remainder);
}

// Reverse the changes made to the digits
for ( int32_t i = 0; i < -order + other.order; ++i ) {
other.digits.erase(digits.begin());
}

for ( int32_t i = 0; i < -other.order + order; ++i ) {
digits.erase(digits.begin());
}

return p_adic(prime, result, all_zero_digits(result) ? ORDER_MAX : std::min(order, other.order));
}

// Return a string representation of this p-adic as a rational number.
std::string convert_to_rational() {
std::vector<uint32_t> numbers = digits;

// Zero
if ( all_zero_digits(numbers) ) {
return "0";
}

// Positive integer
if ( order >= 0 && ends_with(numbers, 0) ) {
while ( numbers.back() == 0 ) {
numbers.pop_back();
}
return std::to_string(convert_to_decimal(numbers));
}

// Negative integer
if ( order >= 0 && ends_with(numbers, prime - 1) ) {
while ( numbers.back() == prime - 1 ) {
numbers.pop_back();
}
negate_digits(numbers);
return "-" + std::to_string(convert_to_decimal(numbers));
}

// Rational
const p_adic copy(prime, digits, order);
p_adic sum(prime, digits, order);
int denominator = 1;
do {
sum = sum.add(copy);
denominator += 1;
} while ( ! ends_with(sum.digits, 0) && ! ends_with(sum.digits, prime - 1) );

const bool negative = ends_with(sum.digits, 6);
if ( negative ) {
negate_digits(sum.digits);
}

std::string numerator = std::to_string(convert_to_decimal(sum.digits));
std::string rational = numerator + " / " + std::to_string(denominator);
return negative ? "-" + rational : rational;
}

// Return a string representation of this p-adic.
std::string to_string() {
while ( digits.size() > PRECISION ) {
digits.pop_back();
}
pad_with_zeros(digits);

std::string result = "";
for ( int64_t i = digits.size() - 1; i >= 0; --i ) {
result += std::to_string(digits[i]);
}

if ( order >= 0 ) {
for ( int32_t i = 0; i < order; ++i ) {
result += "0";
result.erase(result.begin());
}

result += ".0";
} else {
result.insert(result.length() + order, ".");
}

return " ..." + result;
}

private:
/**
* Create a p-adic, with p = prime, directly from a vector of digits.
*
* With aOrder = 0, the vector [1, 2, 3, 4, 5] creates the p-adic ...54321.0
* aOrder > 0 shifts the vector 'aOrder' places to the left and
* aOrder < 0 shifts the vector 'aOrder' places to the right.
*/
p_adic(uint32_t prime, std::vector<uint32_t> digits, int32_t order)
: prime(prime), digits(digits), order(order) {
}

// Transform the given vector of digits representing a p-adic number
// into a vector which represents the negation of the p-adic number.
void negate_digits(std::vector<uint32_t> numbers) {
numbers[0] = prime - numbers[0];
for ( uint64_t i = 1; i < numbers.size(); ++i ) {
numbers[i] = prime - 1 - numbers[0];
}
}

// Return the multiplicative inverse of the given number modulo 'prime'.
uint32_t modulo_inverse(uint32_t number) {
uint32_t inverse = 1;
while ( ( inverse * number ) % prime != 1 ) {
inverse += 1;
}
return inverse;
}

// Return the given number modulo 'prime' in the range 0..'prime' - 1.
int32_t modulo_prime(int64_t number) {
const int32_t div = static_cast<int32_t>(number % prime);
return ( div >= 0 ) ? div : div + prime;
}

// The given vector is padded on the right by zeros up to a maximum length of 'PRECISION'.
void pad_with_zeros(std::vector<uint32_t> vector) {
while ( vector.size() < PRECISION ) {
vector.emplace_back(0);
}
}

// Return the given vector of base 'prime' integers converted to a decimal integer.
uint32_t convert_to_decimal(std::vector<uint32_t> numbers) {
uint32_t decimal = 0;
uint32_t multiple = 1;
for ( const uint32_t& number : numbers ) {
decimal += number * multiple;
multiple *= prime;
}
return decimal;
}

// Return whether the given vector consists of all zeros.
bool all_zero_digits(std::vector<uint32_t> numbers) {
for ( uint32_t number : numbers ) {
if ( number != 0 ) {
return false;
}
}
return true;
}

// Return whether the given vector ends with multiple instances of the given number.
bool ends_with(std::vector<uint32_t> numbers, uint32_t number) {
for ( uint64_t i = numbers.size() - 1; i >= numbers.size() - PRECISION / 2; --i ) {
if ( numbers[i] != number ) {
return false;
}
}
return true;
}

uint32_t prime;
std::vector<uint32_t> digits;
int32_t order;

static const uint32_t PRECISION = 40;
static const uint32_t ORDER_MAX = 1'000;
};

int main() {
std::cout << "2-adic numbers:" << std::endl;
p_adic padicOne(2, -15, 17);
std::cout << "-15 / 17 => " << padicOne.to_string() << std::endl;
p_adic padicTwo(2, 589, 185);
std::cout << "589 / 185 => " << padicTwo.to_string() << std::endl;

p_adic sum = padicOne.add(padicTwo);
std::cout << "sum => " << sum.to_string() << std::endl;
std::cout << "Rational = " << sum.convert_to_rational() << std::endl;
std::cout << std::endl;

std::cout << "7-adic numbers:" << std::endl;
padicOne = p_adic(7, 5, 8);
std::cout << "5 / 8 => " << padicOne.to_string() << std::endl;
padicTwo = p_adic(7, 353, 30809);
std::cout << "353 / 30809 => " << padicTwo.to_string() << std::endl;

sum = padicOne.add(padicTwo);
std::cout << "sum => " << sum.to_string() << std::endl;
std::cout << "Rational = " << sum.convert_to_rational() << std::endl;
std::cout << std::endl;
}
</syntaxhighlight>
{{ out }}
<pre>
2-adic numbers:
-15 / 17 => ...1110000111100001111000011110000111100001.0
589 / 185 => ...0001110100001111001110001011110000110101.0
sum => ...1111111011110001000110101001111000010110.0
Rational = 7238 / 3145

7-adic numbers:
5 / 8 => ...2424242424242424242424242424242424242425.0
353 / 30809 => ...1560462505550343461155520004023663643455.0
sum => ...4315035233123101033613062431266421216213.0
Rational = 156869 / 246472
</pre>


=={{header|FreeBASIC}}==
=={{header|FreeBASIC}}==
Retrieved from "https://rosettacode.org/wiki/P-Adic_numbers,_basic"