Rosetta Code

P-Adic numbers, basic: Difference between revisions

Page Discussion

P-Adic numbers, basic (view source)

Revision as of 09:56, 25 April 2024

1,968 bytes added ,  29 days ago
m
Improbved code.
m (Improved code and added better output example.)
m (Improbved code.)
 
(6 intermediate revisions by the same user not shown)
Line 52:
 
=={{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. p-adic numbers are given corrrect to O(prime^40) and rational reconstructions are accurate to O(prime^20).
<syntaxhighlight lang="c++">
#include <cmath>
#include <cstdint>
#include <iostream>
#include <numeric>
#include <stdexcept>
#include <string>
#include <vector>
 
class p_adicRational {
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 ) {
throw std::invalid_argument("Denominator cannot be zero");
}
 
Line 72 ⟶ 103:
// Process rational zero
if ( numerator == 0 ) {
digits.assign(DIGITS_SIZE, 0);
order = ORDER_MAX;
return;
}
 
// Remove multiples of 'prime' and adjust the order of the p-adicP_adic number accordingly
while ( modulo_prime(numerator) == 0 ) {
numerator /= static_cast<int32_t>(prime);
Line 87 ⟶ 119:
}
 
// Standard calculation of p-adicP_adic digits
const uint64_t inverse = modulo_inverse(denominator);
while ( digits.size() < PRECISIONDIGITS_SIZE ) {
const uint32_t digit = modulo_prime(numerator * inverse);
digits.emplace_back(digit);
Line 95 ⟶ 127:
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;
Line 113 ⟶ 142:
}
 
// Return the sum of this p-adicP_adic number with the given p-adicP_adic number.
p_adicP_adic add(p_adicP_adic other) {
if ( prime != other.prime ) {
throw std::invalid_argument("Cannot add p-adic's with different primes");
}
 
Line 123 ⟶ 152:
std::vector<uint32_t> result;
 
// Adjust the digits so that the p-adicP_adic points are aligned
for ( int32_t i = 0; i < -order + other.order; ++i ) {
other_digits.insert(this_digitsother_digits.begin(), 0);
}
 
Line 141 ⟶ 170:
}
 
return p_adicP_adic(prime, result, all_zero_digits(result) ? ORDER_MAX : std::min(order, other.order));
}
 
// Return athe stringRational representation of this p-adic as a rationalP_adic number.
std::stringRational convert_to_rational() {
std::vector<uint32_t> numbers = digits;
 
// Zero
if ( numbers.empty() || all_zero_digits(numbers) ) {
return "Rational(1, 0");
}
 
// Positive integer
if ( order >= 0 && ends_with(numbers, 0) ) {
whilefor ( numbers.back()int32_t i == 0; i < order; ++i ) {
numbers.pop_backemplace(numbers.begin(), 0);
}
 
return std::to_string(convert_to_decimal(numbers));
return Rational(convert_to_decimal(numbers), 1);
}
 
// Negative integer
if ( order >= 0 && ends_with(numbers, prime - 1) ) {
while ( numbers.back() == prime - 1 ) {
numbers.pop_back();
}
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
const p_adicP_adic copy(prime, digits, order);
p_adicP_adic sum(prime, digits, order);
intint32_t 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);
Line 184 ⟶ 215:
}
 
std::stringint32_t numerator = std::to_string(negative ? -convert_to_decimal(sum.digits) : convert_to_decimal(sum.digits);
 
std::string rational = numerator + " / " + std::to_string(denominator);
if ( order > 0 ) {
return negative ? "-" + rational : rational;
numerator *= std::pow(prime, order);
}
 
if ( order < 0 ) {
denominator *= std::pow(prime, -order);
}
 
return Rational(numerator, denominator);
}
 
// Return a string representation of this p-adicP_adic number.
std::string to_string() {
std::vector<uint32_t> numbers = digits;
while ( digits.size() > PRECISION ) {
pad_with_zeros(numbers);
digits.pop_back();
}
pad_with_zeros(digits);
 
std::string result = "";
for ( int64_t i = digitsnumbers.size() - 1; i >= 0; --i ) {
result += std::to_string(digits[i]);
}
Line 204 ⟶ 241:
for ( int32_t i = 0; i < order; ++i ) {
result += "0";
result.erase(result.begin());
}
 
Line 210 ⟶ 246:
} else {
result.insert(result.length() + order, ".");
 
while ( result[result.length() - 1] == '0' ) {
result = result.substr(0, result.length() - 1);
}
}
 
return " ..." + result.substr(result.length() - PRECISION - 1);
}
 
private:
/**
* Create a p-adicP_adic, with p = 'prime', directly from a vector of digits.
*
* WithFor example: with 'order' = 0, the vector [1, 2, 3, 4, 5] creates the p-adic ...54321.0,
* 'order' > 0 shifts the vector 'order' places to the left and
* 'order' < 0 shifts the vector 'order' places to the right.
*/
p_adicP_adic(const uint32_t& prime, const std::vector<uint32_t>& digits, const int32_t& order)
: prime(prime), digits(digits), order(order) {
}
 
// Transform the given vector of digits representing a p-adicP_adic number
// into a vector which represents the negation of the p-adicP_adic number.
void negate_digits(std::vector<uint32_t>& numbers) {
numbers[0] = modulo_prime(prime - numbers[0]);
for ( uint64_t i = 1; i < numbers.size(); ++i ) {
numbers[i] = prime - 1 - numbers[0i];
}
}
Line 239 ⟶ 279:
uint32_t modulo_inverse(const uint32_t& number) const {
uint32_t inverse = 1;
while ( modulo_prime( inverse * number ) % prime != 1 ) {
inverse += 1;
}
Line 251 ⟶ 291:
}
 
// The given vector is padded on the right by zeros up to a maximum length of 'PRECISIONDIGITS_SIZE'.
void pad_with_zeros(std::vector<uint32_t>& vector) {
while ( vector.size() < PRECISIONDIGITS_SIZE ) {
vector.emplace_back(0);
}
Line 295 ⟶ 335:
static const uint32_t PRECISION = 40;
static const uint32_t ORDER_MAX = 1'000;
static const uint32_t DIGITS_SIZE = PRECISION + 5;
};
 
int main() {
std::cout << "23-adic numbers:" << std::endl;
p_adicP_adic padicOnepadic_one(23, -152, 1787);
std::cout << "-152 / 1787 => " << padicOnepadic_one.to_string() << std::endl;
p_adicP_adic padicTwopadic_two(23, 5894, 18597);
std::cout << "5894 / 18597 => " << padicTwopadic_two.to_string() << std::endl;
 
p_adicP_adic sum = padicOnepadic_one.add(padicTwopadic_two);
std::cout << "sum => " << sum.to_string() << std::endl;
std::cout << "Rational = " << sum.convert_to_rational().to_string() << std::endl;
std::cout << std::endl;
 
std::cout << "7-adic numbers:" << std::endl;
padicOnepadic_one = p_adicP_adic(7, 5, 8);
std::cout << "5 / 8 => " << padicOnepadic_one.to_string() << std::endl;
padicTwopadic_two = p_adicP_adic(7, 353, 30809);
std::cout << "353 / 30809 => " << padicTwopadic_two.to_string() << std::endl;
 
sum = padicOnepadic_one.add(padicTwopadic_two);
std::cout << "sum => " << sum.to_string() << std::endl;
std::cout << "Rational = " << sum.convert_to_rational().to_string() << std::endl;
std::cout << std::endl;
}
Line 323 ⟶ 364:
{{ out }}
<pre>
23-adic numbers:
-152 / 1787 => ...1110000111100001111000011110000111100001101020111222001212021110002210102011122.02
5894 / 18597 => ...0001110100001111001110001011110000110101022220111100202001010001200002111122021.0
sum => ...1111111011110001000110101001111000010110201011000022210220101111202212220210220.02
Rational = 7238154 / 31458439
 
7-adic numbers:
5 / 8 => ...2424242424242424242424242424242424242425424242424242424242424242424242424242425.0
353 / 30809 => ...1560462505550343461155520004023663643455560462505550343461155520004023663643455.0
sum => ...4315035233123101033613062431266421216213315035233123101033613062431266421216213.0
Rational = 156869 / 246472
</pre>
Line 1,647 ⟶ 1,688:
 
=={{header|Java}}==
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. Answersp-adic numbers are given correct to O(prime^40) and the rational reconstruction is correct to O(prime^20).
<syntaxhighlight lang="java">
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.stream.Collectors;
 
public final class PAdicNumbersBasic {
 
public static void main(String[] args) {
System.out.println("3-adic numbers:");
Padic padicOne = new Padic(3, -5, 9);
Line 1,678 ⟶ 1,721:
}
 
final class Padic {
/**
* Create a p-adic number, with p = 'aPrime', from the given rational 'aNumerator' / 'aDenominator'.
*/
public Padic(int aPrime, int aNumerator, int aDenominator) {
if ( aDenominator == 0 ) {
throw new IllegalArgumentException("Denominator cannot be zero");
}
prime = aPrime;
digits = new ArrayList<Integer>(PRECISIONDIGITS_SIZE);
order = 0;
// Process rational zero
if ( aNumerator == 0 ) {
order = ORDER_MAXMAX_ORDER;
return;
}
Line 1,711 ⟶ 1,753:
// Standard calculation of p-adic digits
final long inverse = moduloInverse(aDenominator);
while ( digits.size() < PRECISIONDIGITS_SIZE ) {
final int digit = Math.floorMod(aNumerator * inverse, prime);
digits.addLast(digit);
Line 1,717 ⟶ 1,759:
aNumerator -= digit * aDenominator;
if ( aNumerator =!= 0 ) {
// All successive digits will be zero, which occurs when the denominator is a power of a prime
padWithZeros(digits);
} else {
// The denominator is not a power of a prime
int count = 0;
Line 1,732 ⟶ 1,771:
}
}
}
}
/**
* Return the sum of this p-adic number withand the given p-adic number.
*/
public Padic add(Padic aOther) {
Line 1,743 ⟶ 1,782:
}
List<Integer> result = new ArrayList<Integer>(PRECISION);
// Adjust the digits so that the p-adic points are aligned
for ( int i = 0; i < -order + aOther.order; i++ ) {
aOther.digits.addFirst(0);
}
for ( int i = 0; i < -aOther.order + order; i++ ) {
Line 1,758 ⟶ 1,797:
for ( int i = 0; i < Math.min(digits.size(), aOther.digits.size()); i++ ) {
final int sum = digits.get(i) + aOther.digits.get(i) + carry;
final int remainder = Math.floorMod(sum %, prime);
carry = ( sum >= prime ) ? 1 : 0;
result.addLast(remainder);
Line 1,772 ⟶ 1,811:
}
return new Padic(prime, result, allZeroDigits(result) ? ORDER_MAXMAX_ORDER : Math.min(order, aOther.order));
}
/**
* Return athe stringRational representation of this p-adic as a rational number.
*/
public StringRational convertToRational() {
List<Integer> numbers = new ArrayList<Integer>(digits);
// Zero
if ( numbers.isEmpty() || allZeroDigits(numbers) ) {
return "0new /Rational(0, 1");
}
// Positive integer
if ( order >= 0 && endsWith(numbers, 0) ) {
while for ( numbers.getLast()int i == 0; i < order; i++ ) {
numbers.removeLastaddFirst(0);
}
return String.valueOf(convertToDecimal(numbers));
return new Rational(convertToDecimal(numbers), 1);
}
// Negative integer
if ( order >= 0 && endsWith(numbers, prime - 1) ) {
while ( numbers.getLast() == prime - 1 ) {
numbers.removeLast();
}
negateList(numbers);
for ( int i = 0; i < order; i++ ) {
return "-" + String.valueOf(convertToDecimal(numbers));
numbers.addFirst(0);
}
return new Rational(-convertToDecimal(numbers), 1);
}
Line 1,810 ⟶ 1,851:
sum = sum.add(self);
denominator += 1;
} while ( ! ( endsWith(sum.digits, 0) && !|| endsWith(sum.digits, prime - 1) ) );
final boolean negative = endsWith(sum.digits, 6prime - 1);
if ( negative ) {
negateList(sum.digits);
}
int numerator = negative ? -convertToDecimal(sum.digits) : convertToDecimal(sum.digits);
if ( order > 0 ) {
Line 1,827 ⟶ 1,868:
}
Stringreturn rationalnew = String.valueOfRational(numerator) + " / " +, denominator);
return negative ? "-" + rational : rational;
}
Line 1,834 ⟶ 1,874:
* Return a string representation of this p-adic.
*/
public String toString() {
List<Integer> numbers = new ArrayList<Integer>(digits);
while ( digits.size() > PRECISION ) {
padWithZeros(numbers);
digits.removeLast();
Collections.reverse(numbers);
}
String numberString = numbers.stream().map(String::valueOf).collect(Collectors.joining());
padWithZeros(digits);
StringBuilder builder = new StringBuilder(numberString);
StringBuilder builder = new StringBuilder();
for ( int i = digits.size() - 1; i >= 0; i-- ) {
builder.append(digits.get(i));
}
if ( order >= 0 ) {
for ( int i = 0; i < order; i++ ) {
builder.append("0");
builder.deleteCharAt(0);
}
Line 1,854 ⟶ 1,889:
} else {
builder.insert(builder.length() + order, ".");
while ( builder.toString().endsWith("0") ) {
builder.deleteCharAt(builder.length() - 1);
}
}
return " ..." + builder.toString().substring(builder.length() - PRECISION - 1);
}
Line 1,871 ⟶ 1,910:
prime = aPrime;
digits = new ArrayList<Integer>(aDigits);
padWithZeros(digits);
order = aOrder;
}
/**
* Return the multiplicative inverse of the given decimal number modulo 'prime'.
*/
private int moduloInverse(int aNumber) {
int inverse = 1;
while ( Math.floorMod( inverse * aNumber, prime) % prime != 1 ) {
inverse += 1;
}
Line 1,892 ⟶ 1,930:
*/
private void negateList(List<Integer> aDigits) {
aDigits.set(0, Math.floorMod(prime - aDigits.get(0), prime));
for ( int i = 1; i < aDigits.size(); i++ ) {
aDigits.set(i, prime - 1 - aDigits.get(i));
Line 1,905 ⟶ 1,943:
int multiple = 1;
for ( int number : aNumbers ) {
decimal += number * multiple;
multiple *= prime;
}
Line 1,923 ⟶ 1,961:
*/
private static void padWithZeros(List<Integer> aList) {
while ( aList.size() < PRECISIONDIGITS_SIZE ) {
aList.addLast(0);
}
Line 1,939 ⟶ 1,977:
return true;
}
private static class Rational {
public Rational(int aNumerator, int aDenominator) {
if ( aDenominator < 0 ) {
numerator = -aNumerator;
denominator = -aDenominator;
} else {
numerator = aNumerator;
denominator = aDenominator;
}
if ( aNumerator == 0 ) {
denominator = 1;
}
final int gcd = gcd(numerator, denominator);
numerator /= gcd;
denominator /= gcd;
}
public String toString() {
return numerator + " / " + denominator;
}
private int gcd(int aOne, int aTwo) {
if ( aTwo == 0 ) {
return Math.abs(aOne);
}
return gcd(aTwo, Math.floorMod(aOne, aTwo));
}
private int numerator;
private int denominator;
}
private List<Integer> digits;
private int order;
private final int prime;
private static final int MAX_ORDER = 1_000;
private static final int PRECISION = 40;
private static final int ORDER_MAXDIGITS_SIZE = 1_000PRECISION + 5;
 
}
Line 1,960 ⟶ 2,035:
 
7-adic numbers:
5 / 8 => ...2424242424242424242424242424242424242425424242424242424242424242424242424242425.0
353 / 30809 => ...1560462505550343461155520004023663643455560462505550343461155520004023663643455.0
sum => ...4315035233123101033613062431266421216213315035233123101033613062431266421216213.0
Rational = 156869 / 246472
</pre>
PSNOW123
876

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/363401...363964"