P-Adic numbers, basic: Difference between revisions

Content added Content deleted
(Improved code and added a better output example.)
m (Improved coding.)
Line 52: Line 52:


=={{header|C++}}==
=={{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. Answers are given corrrect to O(prime^20).
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. Answers are given corrrect to O(prime^40).
<syntaxhighlight lang="c++">
<syntaxhighlight lang="c++">
#include <cmath>
#include <cmath>
#include <cstdint>
#include <cstdint>
#include <iostream>
#include <iostream>
#include <numeric>
#include <stdexcept>
#include <stdexcept>
#include <string>
#include <string>
#include <vector>
#include <vector>


class p_adic {
class Rational {
public:
public:
Rational(const int32_t& aNumerator, const int32_t& aDenominator) {
⚫
// Create a p-adic number, with p = 'prime', from the given rational 'numerator' / 'denominator'.
if ( aDenominator < 0 ) {
⚫
p_adic(const uint32_t& prime, int32_t numerator, int32_t denominator) : prime(prime) {
numerator = -aNumerator;
denominator = -aDenominator;
⚫
} else {
numerator = aNumerator;
denominator = aDenominator;
⚫
}

if ( aNumerator == 0 ) {
denominator = 1;
}

const uint32_t divisor = std::gcd(numerator, denominator);
numerator /= divisor;
denominator /= divisor;
}

std::string to_string() const {
return std::to_string(numerator) + " / " + std::to_string(denominator);
}

private:
int32_t numerator;
int32_t denominator;
};

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


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


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


if ( numerator == 0 ) {
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
// The denominator is not a power of a prime
uint32_t count = 0;
uint32_t count = 0;
Line 114: Line 141:
}
}


// Return the sum of this p-adic number with the given p-adic number.
// Return the sum of this P-adic number with the given P-adic number.
p_adic add(p_adic other) {
P_adic add(P_adic other) {
if ( prime != other.prime ) {
if ( prime != other.prime ) {
std::invalid_argument("Cannot add p-adic's with different primes");
std::invalid_argument("Cannot add p-adic's with different primes");
Line 124: Line 151:
std::vector<uint32_t> result;
std::vector<uint32_t> result;


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


return p_adic(prime, result, all_zero_digits(result) ? ORDER_MAX : std::min(order, other.order));
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.
// Return the Rational representation of this P-adic number.
std::string convert_to_rational() {
Rational convert_to_rational() {
std::vector<uint32_t> numbers = digits;
std::vector<uint32_t> numbers = digits;


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


// Positive integer
// Positive integer
if ( order >= 0 && ends_with(numbers, 0) ) {
if ( order >= 0 && ends_with(numbers, 0) ) {
while ( numbers.back() == 0 ) {
for ( int32_t i = 0; i < order; ++i ) {
numbers.pop_back();
numbers.emplace(numbers.begin(), 0);
}
}

return std::to_string(convert_to_decimal(numbers));
return Rational(convert_to_decimal(numbers), 1);
}
}


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

⚫
return Rational(-convert_to_decimal(numbers), 1);
}
}


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


const bool negative = ends_with(sum.digits, 6);
const bool negative = ends_with(sum.digits, 6);
Line 185: Line 214:
}
}


uint32_t numerator = convert_to_decimal(sum.digits);
int32_t numerator = negative ? -convert_to_decimal(sum.digits) : convert_to_decimal(sum.digits);


if ( order > 0 ) {
if ( order > 0 ) {
Line 195: Line 224:
}
}


std::string rational = std::to_string(numerator) + " / " + std::to_string(denominator);
return Rational(numerator, denominator);
return negative ? "-" + rational : rational;
}
}


Line 227: Line 255:
private:
private:
/**
/**
* Create a p-adic, with p = 'prime', directly from a vector of digits.
* Create a P-adic, with p = 'prime', directly from a vector of digits.
*
*
* With 'order' = 0, the vector [1, 2, 3, 4, 5] creates the p-adic ...54321.0
* With 'order' = 0, the vector [1, 2, 3, 4, 5] creates the p-adic ...54321.0
Line 233: Line 261:
* 'order' < 0 shifts the vector 'order' places to the right.
* 'order' < 0 shifts the vector 'order' places to the right.
*/
*/
p_adic(const uint32_t& prime, const std::vector<uint32_t>& digits, const int32_t& order)
P_adic(const uint32_t& prime, const std::vector<uint32_t>& digits, const int32_t& order)
: prime(prime), digits(digits), order(order) {
: prime(prime), digits(digits), order(order) {
}
}
Line 240: Line 268:
// into a vector which represents the negation of the p-adic number.
// into a vector which represents the negation of the p-adic number.
void negate_digits(std::vector<uint32_t> numbers) {
void negate_digits(std::vector<uint32_t> numbers) {
numbers[0] = prime - numbers[0];
numbers[0] = ( prime - numbers[0] ) % prime;
for ( uint64_t i = 1; i < numbers.size(); ++i ) {
for ( uint64_t i = 1; i < numbers.size(); ++i ) {
numbers[i] = prime - 1 - numbers[0];
numbers[i] = prime - 1 - numbers[i];
}
}
}
}
Line 305: Line 333:
static const uint32_t PRECISION = 40;
static const uint32_t PRECISION = 40;
static const uint32_t ORDER_MAX = 1'000;
static const uint32_t ORDER_MAX = 1'000;
static const uint32_t DIGITS_SIZE = PRECISION + 5;
};
};


int main() {
int main() {
std::cout << "3-adic numbers:" << std::endl;
std::cout << "3-adic numbers:" << std::endl;
p_adic padicOne(3, -2, 9);
P_adic padic_one(3, -2, 87);
std::cout << "-2 / 9 => " << padicOne.to_string() << std::endl;
std::cout << "-2 / 87 => " << padic_one.to_string() << std::endl;
p_adic padicTwo(3, 127, 30);
P_adic padic_two(3, 4, 97);
std::cout << "127 / 30 => " << padicTwo.to_string() << std::endl;
std::cout << "4 / 97 => " << padic_two.to_string() << std::endl;


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


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


sum = padicOne.add(padicTwo);
sum = padic_one.add(padic_two);
std::cout << "sum => " << sum.to_string() << std::endl;
std::cout << "sum => " << sum.to_string() << std::endl;
std::cout << "Rational = " << sum.convert_to_rational() << std::endl;
std::cout << "Rational = " << sum.convert_to_rational().to_string() << std::endl;
std::cout << std::endl;
std::cout << std::endl;
}
}
Line 334: Line 363:
<pre>
<pre>
3-adic numbers:
3-adic numbers:
-2 / 9 => ...22222222222222222222222222222222222222.21
-2 / 87 => ...101020111222001212021110002210102011122.2
127 / 30 => ...022002200220022002200220022002200220110.1
4 / 97 => ...1022220111100202001010001200002111122021.0
sum => ...22002200220022002200220022002200220110.01
sum => ...201011000022210220101111202212220210220.2
Rational = 361 / 90
Rational = 154 / 8439


7-adic numbers:
7-adic numbers:
Retrieved from "https://rosettacode.org/wiki/P-Adic_numbers,_basic"