Is there a way to proccess any equation with a fixed memory space/registers?

[Steam Ranger]

This isn't really Amiga specific but coding math in general, is there a way that you can guarantee the ability to proccess ANY equation with a fixed memory space, or would you need a turing machine?

The test case is this:
(Var1 + Var2) * ((Var3 + Var4) * ((Var5 + Var6) * ...
And so on forever.

I was compiling a bit of this on x86_64, it seems the C compiler first used rax rbx rcx rdx, then rsi and rdi, then r* registers.

If you actually made this equation go on foever, would it need infinite memory?

[Karlos]

Originally Posted by Steam Ranger

This isn't really Amiga specific but coding math in general, is there a way that you can guarantee the ability to proccess ANY equation with a fixed memory space, or would you need a turing machine?

The test case is this:
(Var1 + Var2) * ((Var3 + Var4) * ((Var5 + Var6) * ...
And so on forever.

I was compiling a bit of this on x86_64, it seems the C compiler first used rax rbx rcx rdx, then rsi and rdi, then r* registers.

If you actually made this equation go on foever, would it need infinite memory?

The equation can go on forever but the implementation cant. Eventually you would hit a language defined limit for the maximum size of an expression and would have to rethink it.

Eventually you'd probably end up with some loop, tail recursion or plain old recursion. The latter would hit runtime memory limits for the stack. In any event, the compiler would try to make use of the registers for hot variables which were going to be thr temporaries in whatever your implementation is.

[Steam Ranger]

Originally Posted by Karlos

The equation can go on forever but the implementation cant. Eventually you would hit a language defined limit for the maximum size of an expression and would have to rethink it.

Eventually you'd probably end up with some loop, tail recursion or plain old recursion. The latter would hit runtime memory limits for the stack. In any event, the compiler would try to make use of the registers for hot variables which were going to be thr temporaries in whatever your implementation is.

So compilers already have inbuilt limits? Good.

The reason I'm asking is because I'm making a BigInt library (Small and fast enough to run on the Amiga) and I'm adding the C++ interface (I'm coding most of it in C), and I'm trying to figure out how to proccess the kind of free-form equations that C++ allows with classes.

[robinsonb5]

Originally Posted by Steam Ranger

The reason I'm asking is because I'm making a BigInt library (Small and fast enough to run on the Amiga) and I'm adding the C++ interface (I'm coding most of it in C), and I'm trying to figure out how to proccess the kind of free-form equations that C++ allows with classes.

Unless I'm misunderstanding the question, you want to use C++ classes to create a new BigInt type that you can subsequently use in C++ expressions directly, instead of having to use your library's API explicity?

If so, you don't actually need to worry about how to handle expressions - the compiler already knows how to do that. Instead you just need to inform the compiler how to apply certain basic operations - such as addition and subtraction - to the new type you've created. You do this with operator overloading. See https://en.cppreference.com/w/cpp/language/operators

Here's a minimal example that creates a new type of number for which adding them together results in a subtraction! (Only the addition operator is defined so far, so attempting any other kind of operation on a weirdnumber will cause a compilation error.)

#include <iostream>

class weirdnumber
{
    public:
    // Constructors
    weirdnumber() : storage(0)
    {
    };
    weirdnumber(int i) : storage(i)
    {
    };
    // Copy constructor
    weirdnumber(weirdnumber &other) : storage(other.storage)
    {
    };
    // Destructor
    ~weirdnumber()
    {
    };
    // Conversion function
    operator int() const
    {
        return(storage);
    };


    // Overload addition of another weirdnum to this one.
    weirdnumber &operator+=(const weirdnumber &rhs)
    {
        storage-=rhs.storage;
        return(*this);
    };

    // Maybe we want to be able to add an int to a weirdnum, without converting it first...
    weirdnumber &operator+=(int rhs)
    {
        storage-=rhs;
        return(*this);
    };
    

    // These are friend functions rather than member functions because they take two operands
    // and create a third weirdnum as the result.

    // Add two weirdnumbers together
    friend weirdnumber operator+(weirdnumber lhs, const weirdnumber &rhs)
    {
        lhs+=rhs;
        return(lhs);
    };

    // Add a weirdnumber and an int together
    friend weirdnumber operator+(weirdnumber lhs, int rhs)
    {
        lhs+=rhs;
        return(lhs);
    };


    protected:
    int storage;
};


int main(int argc,char **argv)
{
    weirdnumber a(5),b(4);
    std::cout << "weirdnum 5 + weirdnum 4 = " << a+b << std::endl;
    b+=4;
    std::cout << "weirdnum 4 + int 4 = " << b << std::endl;
    std::cout << "weirdnum 0 + int 7 = " << b+7 << std::endl;
    return(0);
}

[Steam Ranger]

Originally Posted by robinsonb5

Unless I'm misunderstanding the question, you want to use C++ classes to create a new BigInt type that you can subsequently use in C++ expressions directly, instead of having to use your library's API explicity?

If so, you don't actually need to worry about how to handle expressions - the compiler already knows how to do that. Instead you just need to inform the compiler how to apply certain basic operations - such as addition and subtraction - to the new type you've created. You do this with operator overloading. See https://en.cppreference.com/w/cpp/language/operators

Here's a minimal example that creates a new type of number for which adding them together results in a subtraction! (Only the addition operator is defined so far, so attempting any other kind of operation on a weirdnumber will cause a compilation error.)

#include <iostream>

class weirdnumber
{
    public:
    // Constructors
    weirdnumber() : storage(0)
    {
    };
    weirdnumber(int i) : storage(i)
    {
    };
    // Copy constructor
    weirdnumber(weirdnumber &other) : storage(other.storage)
    {
    };
    // Destructor
    ~weirdnumber()
    {
    };
    // Conversion function
    operator int() const
    {
        return(storage);
    };


    // Overload addition of another weirdnum to this one.
    weirdnumber &operator+=(const weirdnumber &rhs)
    {
        storage-=rhs.storage;
        return(*this);
    };

    // Maybe we want to be able to add an int to a weirdnum, without converting it first...
    weirdnumber &operator+=(int rhs)
    {
        storage-=rhs;
        return(*this);
    };
    

    // These are friend functions rather than member functions because they take two operands
    // and create a third weirdnum as the result.

    // Add two weirdnumbers together
    friend weirdnumber operator+(weirdnumber lhs, const weirdnumber &rhs)
    {
        lhs+=rhs;
        return(lhs);
    };

    // Add a weirdnumber and an int together
    friend weirdnumber operator+(weirdnumber lhs, int rhs)
    {
        lhs+=rhs;
        return(lhs);
    };


    protected:
    int storage;
};


int main(int argc,char **argv)
{
    weirdnumber a(5),b(4);
    std::cout << "weirdnum 5 + weirdnum 4 = " << a+b << std::endl;
    b+=4;
    std::cout << "weirdnum 4 + int 4 = " << b << std::endl;
    std::cout << "weirdnum 0 + int 7 = " << b+7 << std::endl;
    return(0);
}

But doing things in the typical C++ way would mean tonnes more allocations, de-allocations and other memory management operations that wouldn't be needed if it was implemented manually with functions.

[robinsonb5]

Originally Posted by Steam Ranger

But doing things in the typical C++ way would mean tonnes more allocations, de-allocations and other memory management operations that wouldn't be needed if it was implemented manually with functions.

To a certain extent that's the price one pays for being able to say "a = b + c;" instead of "a=BigInt_Add(b,c)"

Having said that, you can escape some of it by re-writing your expression:
Any time you can say "a+=b" rather than "a+b" you can avoid the creation of an anonymous intermediate object.

In your example "(Var1 + Var2) * ((Var3 + Var4) * ((Var5 + Var6)..."

an anonymous object is created to hold the result of Var1 + Var2, and likewise for Var3 + Var4...
If you don't need the contents of those variables afterwards, you can avoid the creation of the extra object by doing
"(Var1 += Var2) * ((Var3 += Var4) * (Var5 +=Var6)..."
and now the additions don't create anonymous objects any more because they're overwriting the first of each pair of variables. If you likewise replace the "*" with "*=" then there'll be no anonymous object creation, and the final result will replace the contents of Var1.

Of course, by doing that you've sacrificed the elegance and clarity of expression that you were aiming for in the first place, so I'm not advocating it!

(If you *do* need the variables' contents afterwards then you'd have had to use temporary storage even if coding it manually, so the compiler's not being so wasteful after all.)

[paraj]

You can calculate the maximum number of temporary storage necessary (https://docs.lib.purdue.edu/cgi/view...context=cstech) but it can grow arbitrarily large.

Maybe overkill for your application, but the concept of "expression templates" (https://en.wikipedia.org/wiki/Expression_templates) may interest you. Also in C++11 and later you have the "rvalue references" (T&&) that lets you know that the (roughly) that the underlying storage is free to use.
With some, albeit tricky, coding and probably extra rules on the use of the library (e.g. disallowing things like

x += (y * (x += 2))

) you can eliminate most extraneous memory allocations/copies.

Just implementing properly implementing "move semantics" by using the rvalue thing will probably get you like 80% of the way to what you want, since it means that "a = b + c" will do incur at most one memory allocation (when a isn't already large enough to hold the result / aliases a or b).

[Photon]

It's not about size, but precision.

In any language, you can keep precision high and constant.

There's no limit in any language to what you propose, except your selected digits of precision, e.g. 6 digits, or 100, or 100 million.

Possible exceptions are calculations of tau, pi, e, etc where you attempt to set some kind of record. This can and has been done in the 1960s onwards with any CPU that can write to file or printer.

I interpret this question as the ever existing gap between mathematicians and actual implementers, i.e. programmers.

Any computer can calculate anything a mathematician wishes, if he understands enough of how a computer works to break down the problem for a programmer to solve. This was fully understood when computers were created, and was the entire reason for creating them. Mathematics had the formulas but not the results.

With regards to your product of sums, a mathematician would simply not bother with it for very long, and say it tends to infinity very quickly regardless of input values. A mathematician would say it's not worth computing.

Only as a programmer could you embrace infinity, and keep precision within e.g. 13, 100, or a million digits and write the results to file. CPU model is not a problem, a RAM size of at least the desired precision is enough, and it's just math. It's what computers do best.