P-Adic numbers, basic: Difference between revisions
New post.
m (→{{header|Wren}}: Minor tidy) |
(New post.) |
||
Line 1,360:
λ> let x = 2/7 in (2*x - x^2) / 3 :: Rational
8 % 49</pre>
=={{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.
<syntaxhighlight lang="java">
import java.util.ArrayList;
import java.util.List;
public final class PAdicNumbersBasic {
public static void main(String[] args) {
System.out.println("2-adic numbers:");
Padic padicOne = new Padic(2, -25, 13);
System.out.println("-25 / 13 => " + padicOne);
Padic padicTwo = new Padic(2, 571, 151);
System.out.println("571 / 151 => " + padicTwo);
Padic sum = padicOne.add(padicTwo);
System.out.println("sum => " + sum);
System.out.println("Rational = " + sum.convertToRational());
System.out.println();
System.out.println("7-adic numbers:");
padicOne = new Padic(7, 5, 8);
System.out.println("5 / 8 => " + padicOne);
padicTwo = new Padic(7, 353, 30809);
System.out.println("353 / 30809 => " + padicTwo);
sum = padicOne.add(padicTwo);
System.out.println("sum => " + sum);
System.out.println("Rational = " + sum.convertToRational());
}
}
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>(PRECISION);
order = 0;
// Process rational zero
if ( aNumerator == 0 ) {
order = ORDER_MAX;
return;
}
// Remove multiples of 'prime' and adjust the order of the p-adic number accordingly
while ( moduloPrime(aNumerator) == 0 ) {
aNumerator /= prime;
order += 1;
}
while ( moduloPrime(aDenominator) == 0 ) {
aDenominator /= prime;
order -= 1;
}
// Standard calculation of p-adic digits
final long inverse = moduloInverse(aDenominator);
while ( digits.size() < PRECISION ) {
final int digit = moduloPrime(aNumerator * inverse);
digits.addLast(digit);
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;
while ( moduloPrime(aNumerator) == 0 ) {
aNumerator /= prime;
count += 1;
}
for ( int i = count; i > 1; i-- ) {
digits.addLast(0);
}
}
}
}
/**
* Return the sum of this p-adic number with the given p-adic number.
*/
public Padic add(Padic aOther) {
if ( prime != aOther.prime ) {
throw new IllegalArgumentException("Cannot add p-adic's with different primes");
}
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++ ) {
digits.addFirst(0);
}
// Standard digit by digit addition
int carry = 0;
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 = sum % prime;
carry = ( sum >= prime ) ? 1 : 0;
result.addLast(remainder);
}
// Reverse the changes made to the digits
for ( int i = 0; i < -order + aOther.order; i++ ) {
aOther.digits.removeFirst();
}
for ( int i = 0; i < -aOther.order + order; i++ ) {
digits.removeFirst();
}
return new Padic(prime, result, allZeroDigits(result) ? ORDER_MAX : Math.min(order, aOther.order));
}
/**
* Return a string representation of this p-adic as a rational number.
*/
public String convertToRational() {
List<Integer> numbers = new ArrayList<Integer>(digits);
// Zero
if ( allZeroDigits(numbers) ) {
return "0";
}
// Positive integer
if ( order >= 0 && endsWith(numbers, 0) ) {
while ( numbers.getLast() == 0 ) {
numbers.removeLast();
}
return String.valueOf(convertToDecimal(numbers));
}
// Negative integer
if ( order >= 0 && endsWith(numbers, prime - 1) ) {
while ( numbers.getLast() == prime - 1 ) {
numbers.removeLast();
}
negateList(numbers);
return "-" + String.valueOf(convertToDecimal(numbers));
}
// Rational
Padic sum = new Padic(prime, digits, order);
int denominator = 1;
do {
sum = sum.add(this);
denominator += 1;
} while ( ! endsWith(sum.digits, 0) && ! endsWith(sum.digits, prime - 1) );
final boolean negative = endsWith(sum.digits, 6);
if ( negative ) {
negateList(sum.digits);
}
String numerator = String.valueOf(convertToDecimal(sum.digits));
String rational = numerator + " / " + denominator;
return negative ? "-" + rational : rational;
}
/**
* Return a string representation of this p-adic.
*/
public String toString() {
while ( digits.size() > PRECISION ) {
digits.removeLast();
}
padWithZeros(digits);
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);
}
builder.append(".0");
} else {
builder.insert(builder.length() + order, ".");
}
return " ..." + builder.toString();
}
// PRIVATE //
/**
* Create a p-adic, with p = 'aPrime', directly from a list of digits.
*
* With 'aOrder' = 0, the list [1, 2, 3, 4, 5] creates the p-adic ...54321.0
* 'aOrder' > 0 shifts the list 'aOrder' places to the left and
* 'aOrder' < 0 shifts the list 'aOrder' places to the right.
*/
private Padic(int aPrime, List<Integer> aDigits, int aOrder) {
prime = aPrime;
digits = new ArrayList<Integer>(aDigits);
padWithZeros(digits);
order = aOrder;
}
/**
* Return the multiplicative inverse of the given number modulo 'prime'.
*/
private int moduloInverse(int aNumber) {
int inverse = 1;
while ( ( inverse * aNumber ) % prime != 1 ) {
inverse += 1;
}
return inverse;
}
/**
* Return the given number modulo 'prime' in the range 0..'prime' - 1.
*/
private int moduloPrime(long aNumber) {
final int div = (int) ( aNumber % prime );
return ( div >= 0 ) ? div : div + prime;
}
/**
* Transform the given list of digits representing a p-adic number
* into a list which represents the negation of the p-adic number.
*/
private void negateList(List<Integer> aDigits) {
aDigits.set(0, prime - aDigits.get(0));
for ( int i = 1; i < aDigits.size(); i++ ) {
aDigits.set(i, prime - 1 - aDigits.get(i));
}
}
/**
* Return the given list of base 'prime' integers converted to a decimal integer.
*/
private int convertToDecimal(List<Integer> aNumbers) {
int decimal = 0;
int multiple = 1;
for ( int number : aNumbers ) {
decimal += number * multiple;
multiple *= prime;
}
return decimal;
}
/**
* Return whether the given list consists of all zeros.
*/
private static boolean allZeroDigits(List<Integer> aList) {
return aList.stream().allMatch( i -> i == 0 );
}
/**
* The given list is padded on the right by zeros up to a maximum length of 'PRECISION'.
*/
private static void padWithZeros(List<Integer> aList) {
while ( aList.size() < PRECISION ) {
aList.addLast(0);
}
}
/**
* Return whether the given list ends with multiple instances of the given number.
*/
private static boolean endsWith(List<Integer> aDigits, int aDigit) {
for ( int i = aDigits.size() - 1; i >= aDigits.size() - PRECISION / 2; i-- ) {
if ( aDigits.get(i) != aDigit ) {
return false;
}
}
return true;
}
private List<Integer> digits;
private int order;
private final int prime;
private static final int PRECISION = 40;
private static final int ORDER_MAX = 1_000;
}
</syntaxhighlight>
{{ out }}
<pre>
2-adic numbers:
-25 / 13 => ...0100111011000100111011000100111011000011.0
571 / 151 => ...1111111001001101111111001001101111111101.0
sum => ...0100110100010010111010001110101011000000.0
Rational = 3648 / 1963
7-adic numbers:
5 / 8 => ...2424242424242424242424242424242424242425.0
353 / 30809 => ...1560462505550343461155520004023663643455.0
sum => ...4315035233123101033613062431266421216213.0
Rational = 156869 / 246472
</pre>
=={{header|Julia}}==
| |||