Python class for arbitrary-precision natural number

More DRY

Without even delving deep into the code, a cursory overview shows that here is hardly any difference between testBase2, testBase10 and testBase16. It would make sense to merge them to a single, generic function with an additional argument for the base. Your class already has a base argument.

Even if you were writing unit tests, I do not really see a need for separate functions. Did I say unit tests? Yes, that would be nice and you are almost there. Suggested reading for pytest: How to parametrize fixtures and test functions.

Layout

Add line spacing between functions. Inside a class: one line. I like the docstrings.

Class properties

Consider this:

@property
def size(self):
    return len(self.digits)

Then, inside and outside your class you can omit the empty parentheses eg self.size.

As @toolic already mentioned, the string module provides some useful constants. Also some lesser-known ones:

string.hexdigits
'0123456789abcdefABCDEF'
string.octdigits
'01234567'

If you look inside the source code of that module, they are defined like this:

digits = '0123456789'
hexdigits = digits + 'abcdef' + 'ABCDEF'
octdigits = '01234567'

So nothing fancy here.

First of all, I'd like to congratulate you on writing this without using any AIs! Whatever you learn by doing it the hard way, will surely pay dividends later on. In my own experience, current LLMs can be useful when learning a completely new language, but are still extremely brittle for any kind of non-standard algorithms (and even sometimes for code that should be simple). But I would recommend letting (for instance) CoPilot review your code. Code reviews by CoPilot are often extremely helpful. I'd also recommend starting to use a linter, like pylint, flake8 or black and using type annotations (with mypy). Doing this will have an immediate impact on your coding style.

import copy

binary = '01'
octal = '01234567'
decimal = '0123456789'
hexadecimal = '0123456789abcdef'
base64 = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/'

You don't need those constants. Also, in any kind of larger program, using global constants almost invariably leads to bugs. To minimize the risk of bugs, and for readability, it's better to very clearly indicate which names refer to constants, for instance, by putting them in ALL CAPS. The only constant that is special in this code is the base64 one, since with that you introduce your own convention of representation integers in base64 (so that should be documented or at least hinted at in the doc string of the class).

class Natural:

"Natural" is not a very good name. You mean BigInt. The natural numbers are the non-negative integers. The name BigInt would make clear what the purpose of this class is (to support integers of in principle arbitrary size).

"""
A class to represent a nonnegative integer of arbitrary size in any base system.

Attributes:
    digits (list): List of integers where each integer represents position in base string. It represents our arbitrary-sized nonnegative integer starting with least significant digit.
    base (str): String of arbitrary symbols. It represents a custom alphabet for our base system.
    b (int): Length of base string.
"""

It's a bit strange to not also support negative integers, but that's a choice. The attributes of this class should really be hidden since they are implementation details. There is no need for a user of the class to know about them. If so, then they should also not be documented.

In serious code you might at most want to document them in the form of comments, if their meaning or use is not clear from the code itself. Note also that in production it can be extremely annoying to your coworkers -- or your future self -- to document or comment on things that are obvious. As rule of thumb you should ask yourself:

Will I still understand this code when I read it back half a year from now?

And then

If not, shouldn't I then rewrite it so it's clearer?! Or is it just a tiny unclarity or ambiguity that can be solved by adding a short comment?

def __init__(self, input, base=decimal):

You are using a built-in function ("input") as argument name. DO NOT DO THIS. (Did I say that loud enough?) Unfortunately Python allows this, but it's extremely bad style to use built-in function names as argument or variable names. It makes the code harder to read, and can lead to various other issues. Just don't do it. (If you'd have done this in a job interview with me, it would all by itself result in dismissal of you as candidate.)

To specify the base, it seems simpler and clearer to use a single integer as base (that would also conform to how we talk of a base in math, in other words: you're here unnecessarily increasing the mental load of whoever reads the code).

        self.digits = []
        self.base = base
        self.b = len(base)
        if isinstance(input, str):
            if input == '':
                self.digits.append(0)
            else:
                for i in range(len(input) - 1, -1, -1):
                    self.digits.append(self.base[:self.b].index(input[i]))
        elif isinstance(input, int):
            if input == 0:
                self.digits.append(0)
            else:
                while input > 0:
                    self.digits.append(input % self.b)
                    input //= self.b
        elif isinstance(input, list):
            self.digits = input
        else:
            raise ValueError('Your input is not of type str or int or list.')

Okay. First the edge conditions. It's unclear why you would allow an empty string as input arg, but not for instance None. Also, apparently you allow empty lists as input. But your internal represenation of that (digits = []) differs from the representation if the input is an empty string (digits = [0]). So, that's inconsistent. Inconsistencies like this lead to bugs or crashes later on.

Generally, if you have a bunch of "if ... else ..." statements like this, the code will be more readable if you use a match statement instead. (You can import builtins, and match type(x) with case builtins.int, etc.)

To convert an int into a list of digits, it's also clearer if you simply use list(str(x)). In your handling of int inputs, I don't really know anymore what you're doing or trying to do. The code allows an input like 12345 (as int) with base 2. That will surely generate nonsensical results.

For the str-typed inputs, of course the code can also easily crash. While for the list-typed inputs, the input is simply always accepted. So, all this really needs some proper error checking.

The most important issue I have with the code so far is that there is no uniform internal representation of these big ints. That is, the internal representation in the class stays too close to the "surface" representation of the input sequence. This implies that the actual operators (add, sub etc) will also become a lot more complicated. It seems better to me to select a uniform input representation, say with internal constant base 2**32. (Of course, you could also simply use one Python int, since those can become arbitrarily large, but that kind of defeats the purpose of the exercise.) Doing so, you also already don't need to store the base anymore (it's merely an input arg). The only internal field would then be 'digits' (a list of normal integers, 0 <= x < 2**32). For each of the input types (str, list, int, or None) I would then write a little separate conversion helper function that also does proper error checking, so the match code can be tidy and neat. You actually only need one conversion function:

match type(digits):
    case builtins.str:
         self.digits = convert(list(digits), base)
    case builtins.int:
         self.digits = convert(list(reversed(str(digits))), base)
    case builtins.list:
         self.digits = convert(digits, base)
    case _:
        raise TypeError("your error msg here") 

It perhaps a little more appropriate to raise a TypeError, but ValueError is also often used in similar situations.

I'd consider simplifying the constructor code more and pushing all logic into one top-level conversion function that calls the helper function for the different cases. So, in the constructor you would just have:

self.digits = convert(digits, base)

Function 'convert' could be made a static function of the class. Doing so, makes the __init__ simpler, and makes it easier to write unit tests.

In a program like this, type annotations can help to keep the code clear and make it more readable. So, I'd consider using them.

A few observations/suggestions.

Pattern-matching in constructor

I think we can clean up your constructor using pattern-matching. Docstring elided for brevity.

    def __init__(self, input, base=decimal):
        
        self.digits = []
        self.base = base
        self.b = len(base)
        
        match input:
            case '' | 0:
                self.digits.append(0)
            case str(_):
                for i in range(len(input) - 1, -1, -1):
                    self.digits.append(self.base[:self.b].index(input[i]))
            case int(_):
                while input > 0:
                    self.digits.append(input % self.b)
                    input //= self.b
            case list(_):
                self.digits = input
            case _:
                raise ValueError('Your input is not of type str or int or list.')         

I also think that the following might be simplified:

            case str(_):
                for i in range(len(input) - 1, -1, -1):
                    self.digits.append(self.base[:self.b].index(input[i]))

Using reversed:

            case str(_):
                for i in reversed(range(len(input))):
                    self.digits.append(self.base[:self.b].index(input[i]))

We could simply use a slice to reverse the input, but if it's very long you may not wish to create a copy of the list.

            case str(_):
                for d in input[::-1]:
                    self.digits.append(self.base[:self.b].index(d)

Why docstrings are a good idea

In the following, what is flag? I don't see anything that explains what it does.

def testBase10(op, maxn, flag=False):

Further, you have two large chunks of code in each branch of this code. Maybe this really calls for two functions? Except that they appear identical, or at least nearly so. Is this duplication really necessary?

Loops

Setting i to 0, then looping up to a known value, unconditionally incrementing by a constant factor at the end of the loop sure looks like a place to use a for loop over a range.

        result = []
        top, bottom = (self, other) if self > other else (other, self)
        carry = False
        i = 0
        while i < bottom.size():
            x = top.digits[i] + bottom.digits[i]
            if carry:
                x += 1
                carry = False
            if x >= self.b:
                carry = True
            result.append(x - self.b if carry else x)
            i += 1

        result = []
        top, bottom = (self, other) if self > other else (other, self)
        carry = False

        for i in range(bottom.size()):
            x = top.digits[i] + bottom.digits[i]

            if carry:
                x += 1
                carry = False

            if x >= self.b:
                carry = True

            result.append(x - self.b if carry else x)

Further, since you have defined __gt__:

        top, bottom = sorted([self, other], reverse=True)

__str__

Calling a.__str__() looks really un-Pythonic vs. str(a).

String construction

        s = ''
        for i in range(self.size()):
            s = self[i] + s
        return s

Let's use a generator expression and a reversed range.

        return ''.join(self[i] for i in reversed(range(self.size())))

Code organization

First off, imports. Then classes and functions. Then the code you want to execute. But you should be wrapping that in a function and then conditionally calling it.

E.g.

if __name__ == '__main__':
    main()

You may further wish to have your testing code in a separate file.

A few suggestions, especially the last one concerning a different approach to implementation:

Error Messaging

You have in your initializer:

                for i in range(len(input) - 1, -1, -1):
                    self.digits.append(self.base[:self.b].index(input[i]))

You are clearly appending the characters of string input in reverse order to self.digits. But if any character in input is not found in self.base, the call to str.index will raise a ValueError: substring not found exception, which is not particularly meaningful to the client. Also, given how self.base and self.b are related, self.base[:self.b] can be simplified to just self.base. I would replace the above code with:

                for ch in input[::-1]:
                    idx = self.base.find(ch)
                    if idx == -1:
                        raise ValueError(
                            f'Input character {ch!r} is not valid for your specified base.'
                        )
                    self.digits.append(idx)

Naming

Your class is named Natural, but natural what? Wouldn't NaturalNumber be a better name? I would suggest that you rename variable input since it is the name of a built-in function. Likewise, decimal is the name of a standard library module. But all of the bases you have defined at global scope should have names such as DECIMAL_BASE_CHARACTERS. That is, they should be capitalized and appended with _BASE_CHARACTERS to make their semantics clearer and to let us know that they are some pre-defined constants that can be used by clients. You might make them class attributes of NaturalNumber.

PEP 8 Guidelines

You have some very long lines, especially in your docstrings, that could be broken up to keep their length <= 80. You should also have blank lines between your method definitions.

Testing

Include a test where for a given base the input contains an invalid character. This should raise a ValueError exception with a suitable message. Catch the exception and compare its message with what you would expect.

Implementation

Consider the following:

weird = 'αβγδρζξ'

b = Natural('βξ', weird)
x1 = Natural('ββ', weird)
x2 = Natural('βζ', weird)
x3 = Natural('α', weird)
x4 = Natural('ξ', weird)
c = x1 + x2*b + x3*b**2 + x4*b**3

print('weired rexult =', c)
c.change_base(decimal)
print('converted to decimal:', c)

b.change_base(decimal)
x1.change_base(decimal)
x2.change_base(decimal)
x3.change_base(decimal)
x4.change_base(decimal)
c = x1 + x2*b + x3*b**2 + x4*b**3
print('result when first converted to decimal:', c)
c.change_base(weird)
print('result when converted back to weird:', c)

Prints:

weired rexult = ζδξγρ
converted to decimal: 13346
result when first converted to decimal: 13346
result when converted back to weird: ζδξγρ

This suggests that a totally different approach could be taken where the initializer converts the input to a decimal base stored as an int. Then any operation is performed using Python's integer math. The __repr__ method then converts the internal int representation back to a string using the original base.

natural.py

Layout

The docstrings are fantastic. One thing I would change is that some of them are too long. For example:

digits (list): List of integers where each integer represents position in base string. It represents our arbitrary-sized nonnegative integer starting with least significant digit.

This is more reasonable:

digits (list): List of integers where each integer represents position in base string. 
               It represents our arbitrary-sized nonnegative integer starting with least significant digit.

Also consider using type hints to describe input and return types of the functions to make the code even more self-documenting.

The functions should be separated by a blank line. The black program can be used to automatically reformat the code for you.

Comments

The "TODO" comment should be removed. You can keep track of future enhancements in another file in you version control system.

Naming

The PEP 8 style guide recommends all caps for constants. For example, hexadecimal would be HEXADECIMAL.

The variable named input in the __init__ function is the same name as a Python built-in function. This can be confusing. To eliminate the confusion, rename the variable as something more specific. The first clue is that "input" has special coloring (syntax highlighting) in the question, as it does when I copy the code into my editor.

The variable name b is not too descriptive. A longer, more meaningful name would be useful. Also consider creating another function to set base along with its length.

In the change_base function, v is also a short name that does not convey much meaning.

string

Long strings like this are error-prone:

ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789

The string.ascii_letters function provides this for you.

string.digits also gives you 1234567890.

Simpler

In the __pow__ function, this line:

r = r * self

can be simplified as:

r *= self

The same is true of:

k = k + one
k = k - one

natural_test.py

Layout

Move the functions to the top after the import lines. Having them in the middle of the code interrupts the natural flow of the code (from a human readability standpoint).

Documentation

The functions could use docstrings as in your class, especially to describe the inputs. The input flag is too generic.

Magic number

The number 100 is used several times. It would be helpful to use a named constant. That would also allow the code to be more scalable.

DRY

In the testBase10 functions, this line is repeated twice:

print(f'Base 10 test passed for {op} :)')

Since it is the last line in each branch of the if/else, it can be moved after the whole if/else and out-dented.

if flag:

else:

print(f'Base 10 test passed for {op} :)')

There may be other opportunities to reduce repetition.

Performance

Storing an integer as a list of base B digits makes converting to a string maybe slightly faster than storing an int and converting it to string on demand (in __repr__/__str__/__format__). But it makes the math multiple orders of magnitude worse. I'd be a bit surprised if a meaningful size number (say, 64 bits of data each) took less than 100x longer to multiply done the way you're doing it than the same numbers represented as a pair of plain Python ints would take to multiply.

The correct way to do this is to store the value as an int, along with the base. Convert to a string on demand (it might be a little slower, but not meaningfully so most of the time; you just don't stringify numbers that often), and do the actual math with native ints (which are already arbitrary precision) far more efficiently.

Better code reuse and cross-type compatibility

Right now, you've implemented the forward binary operations, e.g. __add__, __mul__, which means two Naturals can work with each other. But frankly, especially once you're storing a single int for the value internally, there's very little reason not to support working with other numeric types.

There's a lot of finicky things to get right to properly support other numeric types, subclasses of your own type, etc., so that both somenumber + plainint and plainint + somenumber both work. Luckily, the CPython folks wrote the fractions.Fraction class as an exemplar for implementing your own numeric types without the massive code duplication a naive approach would involve (implementing __add__ and __radd__ individually, then doing the same for __mul__ and __rmul__, etc., etc.). Take a look at fractions.Fraction's source code, specifically how they implement all the binary operators via a single implementation for each operation that is then converted into both forward and reverse operators using the _operator_fallbacks helper. Note how _operator_fallbacks tests for concrete types that it knows how to handle for sure in the forward method (called first when you're on the left-hand side and the right side is not a subclass of your type, so you only want to do it if you're sure you're correct, and otherwise should return NotImplemented to let the right hand side try), while the reverse method is uses the number ABC tower to test for protocols (because by the time you're called on the right side, it means the left-side didn't know how to handle the operation, so you're the last chance, and should do it if you can). Once that's written, the actual operations can be much simpler, because they know the types have already been checked and converted, so they just need to do the raw math, not the argument parsing work.