The programming thread.

If the devil was a developer:
https://9gag.com/gag/a6qN6zN
This is how he might make user interfaces.

pibbuR who is pretty sure that UI's like this actually does exist.
It has to be said, that AFAIK there is actually no guarantee that every possible combination of digits can be found in PI. Feel free to correct me.

An corollary: The set of integers not divisible by 9 is still an infinite set, and of the same cardinality as the set of all integers.

pibb...buR
 
Joined
Nov 11, 2019
Messages
2,180
Location
beRgen@noRway
It has to be said, that AFAIK there is actually no guarantee that every possible combination of digits can be found in PI. Feel free to correct me.

An corollary: The set of integers not divisible by 9 is still an infinite set, and of the same cardinality as the set of all integers.

pibb...buR
Well, you can now calculate the N'th digit of PI if you want to find out, so you can skip all the known digits ;) :D https://math.hmc.edu/funfacts/finding-the-n-th-digit-of-pi/
 
Joined
Oct 25, 2006
Messages
6,292
Interesting. I will of course try to program it, first using Mathematica and then incorporate it into my developing PibburWorks C++ program.

3.14159bbur
 
Joined
Nov 11, 2019
Messages
2,180
Location
beRgen@noRway
Project Euler (https://projecteuler.net) is a "series of challenging mathematical/computer programming problems that will require more than just mathematical insights to solve. Although mathematics will help you arrive at elegant and efficient methods, the use of a computer and programming skills will be required to solve most problems". Currently there are 826 of them.

I've done one of them: Find the first Fibonacci number with 1000 digits.

I have to admit that I cheated: Mathematica finds Fibonacci numbers very fast, and by the formula IntegerLength[Fibonacci[n]], I quickly found the correct answer to be
4782

Now, how to do it in C++?

Using unsigned long long variables (iteratively or recursively) can only create 20-digit numbers. Using the closed form Binet formula based on the golden ratio additionally suffers from round off errors for floating point numbers.

However, the number of digits can be calculated without calculating the numbers itself using the formula n*Log10(Φ) - Log10(5)/2, where Φ=(1 + √5) / 2. Implementing this worked, and I found the correct answer.

Then I decided that it would be fun to be able to also create the numbers themselves. C++ or its standard libraries do not support arbitrary long integers. So I decided to make my own big integer class. There are a number of 3rd party libraries out there, no doubt far better than what I can do. But since I'm doing this for fun, I'm doing it myself ATM, of course switching to the good ones if needed at a later stage.

Currently my big integer class handles only addition, but for Fibonacci, that's all I need. Creating the numbers from one up to the 1000-digit number takes 5 seconds, which isn't too bad methinks. Can't compete with Mathematica of course, which creates the numbers up to the 20000th (4180 digits) in a second.

pibbuR.size();

PS. I may, just for fun, also see what Maple and Matlab can do. Stay in tune. DS
 
Last edited:
Joined
Nov 11, 2019
Messages
2,180
Location
beRgen@noRway
Project Euler (https://projecteuler.net) is a "series of challenging mathematical/computer programming problems that will require more than just mathematical insights to solve. Although mathematics will help you arrive at elegant and efficient methods, the use of a computer and programming skills will be required to solve most problems". Currently there are 826 of them.

I've done one of them: Find the first Fibonacci number with 1000 digits.

I have to admit that I cheated: Mathematica finds Fibonacci numbers very fast, and by the formula IntegerLength[Fibonacci[n]], I quickly found the correct answer to be
4782

Now, how to do it in C++?

Using unsigned long long variables (iteratively or recursively) can only create 20-digit numbers. Using the closed form Binet formula based on the golden ratio additionally suffers from round off errors for floating point numbers.

However, the number of digits can be calculated without calculating the numbers itself using the formula n*Log10(Φ) - Log10(5)/2, where Φ=(1 + √5) / 2. Implementing this worked, and I found the correct answer.

Then I decided that it would be fun to be able to also create the numbers themselves. C++ or its standard libraries do not support arbitrary long integers. So I decided to make my own big integer class. There are a number of 3rd party libraries out there, no doubt far better than what I can do. But since I'm doing this for fun, I'm doing it myself ATM, of course switching to the good ones if needed at a later stage.

Currently my big integer class handles only addition, but for Fibonacci, that's all I need. Creating the numbers from one up to the 1000-digit number takes 5 seconds, which isn't too bad methinks. Can't compete with Mathematica of course, which creates the numbers up to the 20000th (4180 digits) in a second.

pibbuR.size();

PS. I may, just for fun, also see what Maple and Matlab can do. Stay in tune. DS
Wow, it sounds really fun to be retired, I'd never have time for this sort of cool things!
 
Joined
Oct 25, 2006
Messages
6,292
Project Euler (https://projecteuler.net) is a "series of challenging mathematical/computer programming problems that will require more than just mathematical insights to solve. Although mathematics will help you arrive at elegant and efficient methods, the use of a computer and programming skills will be required to solve most problems". Currently there are 826 of them.

I've done one of them: Find the first Fibonacci number with 1000 digits.
Thanks for the link, it looks interesting!

Ah, you have to find the index of that Fibonacci number, not the number itself. I was starting to wonder what I was missing. ;)

That's a nice trick! You need enough general knowledge on series to come up with that I guess.

5 seconds seems pretty fast indeed. It's tempting to try in Rust but I'd probably cheat and use the bigdecimal crate. Did you store your big integer values as decimal digits, or as a large binary value?

On a cousin-related note, I'm busy implementing a library to ... display floating-point numbers. In Rust, of course. The default routines are fine but I realized that they didn't round properly when specifying the precision (for ex. "%.4f" in C). I learned a lot of things, the two main being:
  • The CPU and most well-behaved libraries round "tie to even", also called "banker's rounding". So 3.5 rounded as an integer becomes 4 (even), but 4.5 becomes 4 (even) too. I had no idea, never learned that before despite advanced courses on calculus error propagation. The reason is of course to lower the bias when there are many operations.
  • It's also where many language fail to properly round with ".{digit}f" because they store numbers in binary (b0*1/2 + b1*1/4 + ...) and values like 0.1 cannot be represented exactly. So converting floating-point numbers to strings is actually very complex and there are many algorithms trying to represent them "nicely" (for example "0.1" while the actual binary value is slightly different). It's still being worked on, they have funny names like DragonBox, Schubfach, Ryu, Grisu/Dragon4...
So I implemented one of those algorithms (Schubfach) and did the proper rounding when it's requested. Now it's faster and more reliable than the standard library, which is nice. :)
 
Joined
Aug 29, 2020
Messages
10,372
Location
Good old Europe
Thanks for the link, it looks interesting!

Ah, you have to find the index of that Fibonacci number, not the number itself. I was starting to wonder what I was missing. ;)

5 seconds seems pretty fast indeed. It's tempting to try in Rust but I'd probably cheat and use the bigdecimal crate. Did you store your big integer values as decimal digits, or as a large binary value?
:)
Yes, I see I was a bit unclear about finding the index or the number itself.

I store the values as a dynamic list of unsigned long elements, with values limited to 1.000.000.000.

A large binary value is interesting, and I will look into it. In fact I think there is a lot to be learned from improving the class. As for big decimals, that comes next. I guess it's fairly easy to implement it as a pair of big integers.

But first, I have to implement subtractions, multiplication and division. Mathematical functions like trigonometry may be over my head, although at least some of them can be implemented using Taylor expansion. I guess that when that time comes, I should find an existing library.

pibbuR
 
Joined
Nov 11, 2019
Messages
2,180
Location
beRgen@noRway
A large binary value is interesting, and I will look into it. In fact I think there is a lot to be learned from improving the class. As for big decimals, that comes next. I guess it's fairly easy to implement it as a pair of big integers.

But first, I have to implement subtractions, multiplication and division. Mathematical functions like trigonometry may be over my head, although at least some of them can be implemented using Taylor expansion. I guess that when that time comes, I should find an existing library.

pibbuR
That must be the fun part. ;)

If you already own Hacker's Delight, there are a few pages on multiplication and division, but don't buy the book just for that, it's not the main subject (unless you like the content - optimization of a series of algorithms). The code is public though (link).

It may be tricky to represent decimal numbers as a pair of numbers if you require very large and very small numbers with a "*10^n" representation. Otherwise I've done a little of that in a fixed-point class and it's fine for arithmetic operations, it's only a larger int with a decimal point somewhere that requires additional shifting when multiplying and so on.

If you're interested, there are two "well-known" libraries implementing IEEE 754-2008 Decimal Floating-Point - so an exact representation of decimal numbers and not the binary version we all know in IEEE-754 float & double. It's still limited to max 128 bits, so not infinite. One made by Intel (link - MIT-like licence), and another one made/contributed by IBM (link - GPL). It's hard to build though, at least on Windows. Intel's is full of tables and takes more space but is quicker - at least on Intel computers, strangely. The other may be easier to read but don't take my word for it.

If you look at them, you'll see how they do for those trig/hyperbolic trig functions, and you were right about the approach. Here IBM's code:

C:
decNumber* decNumberSin (decNumber *_result, decNumber *y, decContext *set)
{
  decNumber pi, pi2, zero, one, two, x, fctl, term, cmp, result;
  int i;
  int negate = 0;

  DEC_STASH_CONTEXT (set, &zero);

  decNumberFromString (&one, "1", set);
  decNumberFromString (&two, "2", set);
  decNumberFromString (&pi,  PI , set);

  // Copy the argument y, so we can modify it.
  decNumberCopy (&x, y);
  // sin -x = - sin x
  /* if (decCompare (&x, &zero) < 0) { */
  if (decNumberIsNegative (&x)) { // x < 0
    decNumberMinus (&x, &x, set);
    negate = 1;
  }
  // We now have x >= 0
  decNumberMultiply (&pi2, &pi, &two, set); // pi2 = 2*pi
  decNumberMod (&x, &x, &pi2, set);
  // We now have 0 <= x < 2*pi
  /*if (decCompare (&x, &pi) >= 0) {*/
  decNumberCompare (&cmp, &x, &pi, set);
  if (!decNumberIsNegative (&cmp)) {
    // x >= pi
    decNumberSubtract (&x, &x, &pi, set);
    negate = 1-negate;
  }
  // We now have 0 <= x < pi
  decNumberDivide (&pi2, &pi, &two, set); // pi2 = pi/2
  /*if (decCompare (&x, &pi2) >= 0) {*/
  decNumberCompare (&cmp, &x, &pi2, set);
  if (!decNumberIsNegative (&cmp)) {
    // x >= pi/2, so let x = pi-x
    decNumberSubtract (&x, &pi, &x, set);
  }
  // We now have 0 <= x <= pi/2.

  //             x^3   x^5    x^7
  // sin x = x - --- + --- - ---- + ...
  //              6    120   5040
  //
  // term(0) = x
  // term(i) = - term(i-1) * x^2 / ((2*i)*(2*i+1))

  decNumberCopy (&fctl, &one);
  decNumberCopy (&term, &x);
  decNumberCopy (&result, &x);
  // DECNUMDIGITS+3 terms are enough to achieve the required precision.
  for (i=0; i<DECNUMDIGITS+3; i++) {
    decNumber tmpd, termout;

    // term = -term * x^2 / (cnt*(cnt+1))
    // cnt = cnt+2
    decNumberMinus (&term, &term, set);
    decNumberMultiply (&term, &term, &x, set);
    decNumberMultiply (&term, &term, &x, set);

    // Compute denominator and generate term.
    decNumberFromInt32 (&tmpd, ((i+1)*2 + 1) * ((i+1)*2));
    decNumberMultiply (&fctl, &fctl, &tmpd, set);
    decNumberDivide (&termout, &term, &fctl, set);

    // sum = sum + term
    decNumberAdd (&result, &result, &termout, set);
  }
  if (negate) {
    decNumberMinus (&result, &result, set);
  }
  DEC_RESTORE_ROUND (set, _result, &result, &zero)
  return _result;
} /* decNumberSin  */
 
Joined
Aug 29, 2020
Messages
10,372
Location
Good old Europe
@pibbuR : look for cryptographic libraries, there it is routine to calculate with integers of arbitrary length, e.g. for RSA or elliptic curve algorithms.
 
Joined
Dec 26, 2007
Messages
1,794
I'm trying to call my math packages from C++. Very easy to connect to Matlab (probably also Mathematica), but I'd like to also connect to open source packages like Octave (7.30). Which is very difficult. I've followed a couple of (not very updated) guidelines using Visual Studio, but I get compile errors from Octave headers like missing variables and illegal type casts. I did get it to work (AFAIK) with c#.

Has anyone any experience with calling Octave from C++.

pibbuR
 
Joined
Nov 11, 2019
Messages
2,180
Location
beRgen@noRway
I'm trying to call my math packages from C++. Very easy to connect to Matlab (probably also Mathematica), but I'd like to also connect to open source packages like Octave (7.30). Which is very difficult. I've followed a couple of (not very updated) guidelines using Visual Studio, but I get compile errors from Octave headers like missing variables and illegal type casts. I did get it to work (AFAIK) with c#.

I have never tried that, but I thought that Octave was compiled with gcc, so does it mean you are using Visual Studio with gcc?
 
Joined
Aug 29, 2020
Messages
10,372
Location
Good old Europe
I have never tried that, but I thought that Octave was compiled with gcc, so does it mean you are using Visual Studio with gcc?
Not sure if I understand the question. I installed Octave using a Windows installer, so I'm not compiling Octave. I'm just trying to link C++ programs to it. Visual Studio/MSVC shouldn't have problems with that, at least I haven't found anything indicating that on the web. (And for what it's worth: using C# with Octave works very well, so Octave should be familiar with the VS environment). And as far as I know (I can be wrong of course) MSVC is among the better compilers when it comes to following standards. At the very least it implemented full support for C++20 before any other of the well known compilers.

The problem is that header files needed for using Octave in C++ programs (among others <octave/oct.h> gives compiler errors.

BTW: Just found another link which seems a bit more to the point. I'll see what I can get out of that and come back to you. However, since linking works with Matlab, and I have a Matlab license, it's no big deal if I can't get Octave to work. So maybe I'll drop it and stick to the Matlab interface. And later interfacing with Mathematica and Maple (I have all of them, they're quite cheap for hobby users).

pibbuR

PS. I can of course try to call Octave using C++11, in case problems are caused by number 20 features. If that's the case, however, I won't use Octave, as the code I write in general uses C++20 things. DS.

PPS. There is of courser the possibility that I've missed a few things that I should have thought of. I had problems with linking Matlab until I discovered two very embarrassing errors in my Matlab linking setup. DS.

PS. No, I won't tell you. DS.
 
Last edited:
Joined
Nov 11, 2019
Messages
2,180
Location
beRgen@noRway
Probably too obvious, but may be you need to include some header files or set some paths so your linker finds all definitions it needs? Also may be the libraries for C# and C++ are different?
Another thought: My experience is, that you find solutions for nearly all problems using google. So may be you google for Octave together with some of the error messages you get?
 
Joined
Dec 26, 2007
Messages
1,794
It's the compiler that complains, don't reach as far as the linker. And it's the Octave header files which seemingly is in error. No, I don't believe the Octave developers have made these obvious types of error in their code, so there must be something else. Very likely something I've missed. Missing header files? Maybe, but I've tried supposedly complete examples from the net which are supposed to work.

I fact, I have found very little concrete information on the net, and most of what I've found is based on significantly older versions of Octave. Except the one I mentioned just having found, and haven't yet had the time to look at.

One more thing: Most of the web sites I've found is about Linux Octave. So maybe I should try that.

Thanks to both you and the Red Glyph.

pibbur
 
Joined
Nov 11, 2019
Messages
2,180
Location
beRgen@noRway
Not sure if I understand the question. I installed Octave using a Windows installer, so I'm not compiling Octave. I'm just trying to link C++ programs to it. Visual Studio/MSVC shouldn't have problems with that, at least I haven't found anything indicating that on the web. (And for what it's worth: using C# with Octave works very well, so Octave should be familiar with the VS environment). And as far as I know (I can be wrong of course) MSVC is among the better compilers when it comes to following standards. At the very least it implemented full support for C++20 before any other of the well known compilers.

The problem is that header files needed for using Octave in C++ programs (among others <octave/oct.h> gives compiler errors.

BTW: Just found another link which seems a bit more to the point. I'll see what I can get out of that and come back to you. However, since linking works with Matlab, and I have a Matlab license, it's no big deal if I can't get Octave to work. So maybe I'll drop it and stick to the Matlab interface. And later interfacing with Mathematica and Maple (I have all of them, they're quite cheap for hobby users).

pibbuR

PS. I can of course try to call Octave using C++11, in case problems are caused by number 20 features. If that's the case, however, I won't use Octave, as the code I write in general uses C++20 things. DS.

PPS. There is of courser the possibility that I've missed a few things that I should have thought of. I had problems with linking Matlab until I discovered two very embarrassing errors in my Matlab linking setup. DS.

PS. No, I won't tell you. DS.
Can you post the error? Typically an include file should include all include files it require but sometime they forget. Also they sometime use name spaces without declaring them. There are so many minor possibilities nothing can be said fer sure without the error message. Of course sometimes they actually have syntax errors ;)
 
Joined
Jun 26, 2021
Messages
297
Not sure if I understand the question. I installed Octave using a Windows installer, so I'm not compiling Octave. I'm just trying to link C++ programs to it. Visual Studio/MSVC shouldn't have problems with that, at least I haven't found anything indicating that on the web. (And for what it's worth: using C# with Octave works very well, so Octave should be familiar with the VS environment). And as far as I know (I can be wrong of course) MSVC is among the better compilers when it comes to following standards. At the very least it implemented full support for C++20 before any other of the well known compilers.
What I mean is that (I think) Octave is meant to be compiled with gcc, so the sources are for GNU tools and the libraries too. The same is probably true of the headers they provide to link and interface external code, but I may be wrong.

In theory C++ is standard, but in practice I've never found gcc source to be compatible with MSVC. First because MSVC has never entirely followed the standard (unless that has changed in the last ~5 years), so for example things like static inline are not recognized.

Then the header files of the standard library are organized differently and use different predefined macros. Unless the header files in Octave take this into account - and for the right version of MSVC - you'll get problems because of that. Good libraries try to make their headers as universal as possible but it's a lot of work.

To rule that out, you could do a quick test by installing MinGW and trying to compile from there, see if that makes any difference. Or WSL (Window Subsystem for Linux). Or test on a Linux machine if you have one, real or virtual. But for those 2 last options, you'll need the Linux version of Octave of course, and the headers might be different...

C# and .NET were originally designed for Windows. A subset is available for Linux and other platforms through Mono, the .NET framework ported by Ximian, then Novell (supported financially by MS), and now taken over by Xamarin. So it's probably normal that this part works better, it's more "standard".
 
Last edited:
Joined
Aug 29, 2020
Messages
10,372
Location
Good old Europe
static inline is supported now.

If you look at https://en.cppreference.com/w/cpp/compiler_support, you will see at for C++20, MSVC is the only compiler that supports all of it completely. Gcc comes very close, the only exception now is incomplete support for modules. For older C++ versions, Gcc and MSVC are about the same, with a few exceptions here and there.

What I will do: Try it on Linux. Eventually. But for now I'm going for Matlab (and the other two).

pibbuR
 
Joined
Nov 11, 2019
Messages
2,180
Location
beRgen@noRway
PS: I've just downloaded Octave for Windows to have a quick look, and sure enough, it comes with MinGW. So you don't even have to install it, you can launch a shell with msys2_shell.cmd. There's no compiler, so you'll have to install it with pacman. Hum. That seems a little... that's what I did:

$ pacman -Sy
(wait for it to synchronize its databases)
$ pacman -Ss gcc
(gives a healthy list of candidates, so that seems fine so far)
$ pacman -Syu gcc
(seems to update and install a lot of things)
$ gcc --version
gcc (GCC) 11.3.0
Copyright (C) 2021 Free Software Foundation, Inc.
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

And make is there too, but perhaps you need more tools. EDIT: like cmake? You can install it the same way with pacman -S cmake (ou -Syu but that's not necessary if you do it right after the other, it's just to update at the same time).

For information, your home directory is in Octave's directory, under home/<username>. So you can cd ../.. to be in Octave's directory.
 
Joined
Aug 29, 2020
Messages
10,372
Location
Good old Europe
In case you're interested:

The Wolfram engine, the power behind Mathematica is freely available for pre-production software development. (https://www.wolfram.com/engine/).

You can
  • Develop a product for yourself or your company
  • Conduct personal projects at home, at school, at work
  • Explore the Wolfram Language for future production projects
I'm currently working to link C++ programs to the engine. I've got a working version, but it is a bit cumbersome at the moment.

Pibbur[s_] := "Hello " <> s

EDIT: You can actually also use it to enter and evaluate expressions, using a command line interface.
 
Last edited:
Joined
Nov 11, 2019
Messages
2,180
Location
beRgen@noRway
Back
Top Bottom