1. Can OpenEuphoria Help Solve This?

The Uncracked Number Problem

I seem to recall a "Big Num" library from long ago. Maybe you'll need that. grin

Good luck!

P.S. The follow up video: 74 is cracked

new topic     » topic index » view message » categorize

2. Re: Can OpenEuphoria Help Solve This?

euphoric said...

The Uncracked Number Problem

I seem to recall a "Big Num" library from long ago. Maybe you'll need that. grin

Good luck!

P.S. The follow up video: 74 is cracked

I'm a big fan of Brady Haran, especially Numberphile and Objectivity. I recommend his podcasts as well, if that's your thing: Hello Internet and The Unmade Podcast.

But I would say that, no, Euphoria is probably not well suited for this, at least in its current state.

These types of brute-force problems require massively parallel systems that can crunch numbers at an astronomical rate.

I supposed you could probably get something going using a message queuing system of some sort, and then scale it out to however many nodes you want working on the problem.

But at that rate, if you want the fastest possible speed, you'd probably use C or Assembly directly on a big CPU, like a Ryzen or Core i9.

There are a couple big number libraries in the archive. I also have a wrapper for tiny-bignum-c if anyone is interested.

-Greg

new topic     » goto parent     » topic index » view message » categorize

3. Re: Can OpenEuphoria Help Solve This?

ghaberek said...

But at that rate, if you want the fastest possible speed, you'd probably use C or Assembly directly on a big CPU, like a Ryzen or Core i9.

Since we can translate/compile, aren't we essentially using C?

new topic     » goto parent     » topic index » view message » categorize

4. Re: Can OpenEuphoria Help Solve This?

euphoric said...
ghaberek said...

But at that rate, if you want the fastest possible speed, you'd probably use C or Assembly directly on a big CPU, like a Ryzen or Core i9.

Since we can translate/compile, aren't we essentially using C?

That's a good question. If we compile a small C program, say, "hello world", we get a very small executable, less than 9,000 bytes.

The same thing in compiled Eu is over 200,000 bytes. Seems unlikely that it would run as fast, and certainly would take longer to load (but not enough to notice).

So, yeah, it's 'C', but not necessarily the most efficient C, I'd guess.

new topic     » goto parent     » topic index » view message » categorize

5. Re: Can OpenEuphoria Help Solve This?

euphoric said...

Since we can translate/compile, aren't we essentially using C?

Oh boy, that's a loaded question. Like Irv said, yes it's C but it's not hand-written C.

The compiler does a pretty good job of optimizing what the translator spits out, but if you hand-converted your Euphoria code to C it would still be measurably faster. I'm guessing at least 10-15%.

With hand-written C you can tune the crap out of it and use threading, or by inserting hand-coded inline assembly, or with stupid C tricks like Duff's device.

Plus there are better languages out there for expressing and solving big math problems, like R or OCaml.

And if you want to get as much speed as possible, using OpenCL or Vulkan will yield amazing results by leveraging modern GPUs.

-Greg

new topic     » goto parent     » topic index » view message » categorize

6. Re: Can OpenEuphoria Help Solve This?

I've tried a few simple tests, and Euphoria (compiled) runs anywhere from 70 percent of the speed of the equivalent C code, up to 110 percent (iow - faster than C!)

It all depends upon what the test does. In real life, there would be a mix of the slower operations with the faster, so I wouldn't expect better than 70 percent or so.

Interestingly enough, in some selected instances, the interpreted Eu code runs nearly as fast as compiled C, also, but 25 percent is more realistic.

new topic     » goto parent     » topic index » view message » categorize

7. Re: Can OpenEuphoria Help Solve This?

irv said...

I've tried a few simple tests...

Whoa! That's cool, Irv. You should post a Wiki article about those tests.

new topic     » goto parent     » topic index » view message » categorize

8. Re: Can OpenEuphoria Help Solve This?

irv said...

....up to 110 percent (iow - faster than C!)

Is it possible? If Euphoria translates to C then it means that C is faster than... C. The translation process can make the result slower, but can't make it faster than similar program written directly in a language the code is translated to. I'm still new to Euphoria (I may be doing things the wrong way), but all I got after compilation are programs that run max. 2 times faster than Eui and are significantly slower than code translated by Nim or run by Lujit. On 32-bit machine, sometimes they were even slower! Maybe we should start a new topic about it, but I would like to see examples of code that runs significantly faster after compilation and is as fast as C or Luajit.

new topic     » goto parent     » topic index » view message » categorize

9. Re: Can OpenEuphoria Help Solve This?

Pirx said...

...all I got after compilation are programs that run ... significantly slower than code translated by Nim or run by Luajit.

I remember first encountering Lua and really liking it. I wonder how long it's been. I should check it out.

Lua is as versatile as OpenEuphoria, isn't it? Maybe even moreso, if Lua apps can run on mobile devices.

new topic     » goto parent     » topic index » view message » categorize

10. Re: Can OpenEuphoria Help Solve This?

euphoric said...

Lua is as versatile as OpenEuphoria, isn't it? Maybe even moreso, if Lua apps can run on mobile devices.

Lua is an embedded language, so is much simpler than Eeuphoria. The language itself is tiny and it comes with minimal standard library. There are several Lua distributions (Ulua, LuaPower, LuaDist, LuaForWindows) that come with batteries included, but some of the libraries are limited and/or not in development any more. You can use Lua to create Android apps. There is an Android version of LOVE, extremely easy to use 2D game engine. You can also use something like Corona to write different types of mobile apps. Lua is fast and the jit implementation is extremely fast. I would say that Euphoria is something between Lua and Python or Ruby.

new topic     » goto parent     » topic index » view message » categorize

11. Re: Can OpenEuphoria Help Solve This?

Pirx said...

Is it possible? ... but I would like to see examples of code that runs significantly faster after compilation and is as fast as C or Luajit.

Many years ago I started a blog that I never kept up. The one and only entry might interest you: http://phix.x10.mx/blog.php

In short, modifying data (the for loop control variable) was touching the same #400-byte memory page the code was on, forcing the CPU to re-load the code cache.
I very much doubt it is anything similar (C was not involved in that example, and I fixed that issue 8 years ago), but the point is made that computers often do strange low-level things.

Pete

new topic     » goto parent     » topic index » view message » categorize

12. Re: Can OpenEuphoria Help Solve This?

I just ran "fannkuch" and "nbody" benchmarks on my netbook.

Phix compiled can be about the same speed as LuaJIT, while OE compiled can be respectably close.

If you waste enough time with different arguments you can generate a variety of results.

The best criteria is that we create programs faster/easier using atom/sequence thinking.

_tom

new topic     » goto parent     » topic index » view message » categorize

13. Re: Can OpenEuphoria Help Solve This?

_tom said...

Phix compiled can be about the same speed as LuaJIT, while OE compiled can be respectably close.

This is something strange. I just run simple script calculating 10000 numbers of PI and the results on my laptop are:

Euphoria (interpreted):

real 0m18.926s user 0m18.820s sys 0m0.072s

Euphoria (compiled):

real 0m9.464s user 0m9.333s sys 0m0.064s

Luajit

real 0m0.970s user 0m0.944s sys 0m0.010s

As you can see Luajit is 10 times faster than compiled Euphoria and 20 times faster than interpreted Euphoria. Also, compiled Euphoria code seems to run with two different speeds. It's very fast at the beginning then suddenly slows down. Strange...

new topic     » goto parent     » topic index » view message » categorize

14. Re: Can OpenEuphoria Help Solve This?

Phix has a way of being faster than OE.

The Phix algorithm from Rosetta Code:

integer a,b,c,d,e,g sequence f a=10000 f=repeat(floor(a/5) 
,8401) c=8400 e=0 while c>0 do g=2*c d=0 b=c while b>0 do  
d+=f[b]*a g-=1 f[b]=remainder(d, g) d=floor(d/g) g-=1 b-=1  
if b!=0 then d*=b end if end while printf(1,"%04d",e+floor 
(d/a)) c-=14 e = remainder(d,a) end while 

From Lua Rosetta Code:

a = {} 
n = 1000 
len = math.modf( 10 * n / 3 ) 
  
for j = 1, len do 
    a[j] = 2 
end 
nines = 0 
predigit = 0 
for j = 1, n do 
    q = 0 
    for i = len, 1, -1 do 
        x = 10 * a[i] + q * i 
        a[i] = math.fmod( x, 2 * i - 1 ) 
        q = math.modf( x / ( 2 * i - 1 ) ) 
    end 
    a[1] = math.fmod( q, 10 ) 
    q = math.modf( q / 10 ) 
    if q == 9 then 
        nines = nines + 1 
    else 
        if q == 10 then 
            io.write( predigit + 1 ) 
            for k = 1, nines do 
                io.write(0) 
            end 
            predigit = 0 
            nines = 0 
        else 
            io.write( predigit ) 
            predigit = q 
            if nines ~= 0 then 
                for k = 1, nines do 
                    io.write( 9 ) 
                end 
                nines = 0 
            end 
        end 
    end 
end 
print( predigit ) 

The test method:

atom t 
 
printf(1, "Phix\n" ) 
t = time() 
system( "p p_pi.ex" ) 
? time() - t 
 
printf(1, "\nPhix Compiled\n" ) 
-- you get a compiled program with: p -c p_pi.ex 
 
t = time() 
system( "./p_pi" ) 
? time() - t 
 
printf(1, "\nLuaJIT\n" ) 
t = time() 
system( "luajit pi.lua" ) 
? time() - t 

The test hardware:

  • hp netbook (atom!)
  • Bodhi Linux

The results

Phix is three time faster than LuaJIT.

Enough of a test, on my machine, to make Phix or OE preferable to Lua. It is also true that many programmers would choose Lua if Euphoria was not available.

_tom

new topic     » goto parent     » topic index » view message » categorize

15. Re: Can OpenEuphoria Help Solve This?

_tom said...

The best criteria is that we create programs faster/easier using atom/sequence thinking.

Amen to that.

new topic     » goto parent     » topic index » view message » categorize

16. Re: Can OpenEuphoria Help Solve This?

_tom, you are comparing two different algorithms. I implemented the same algorithm in Lua and Euphoria (the code is, in most parts, identical). But that's not the point. I believe that compiled code runs much faster on other people's computers. I just don't know why it's so slow on my machine. It doesn't make sense. Compiled code is sometimes slower than the interpreter. The same happens on 32-bit SparkyLinux (based on Debian) and 64-bit Solus. Phix, on the other hand, doesn't work on them at all - segmentation fault is all I get. They are rolling release distros. I don't know on how old distro the Euphoria and Phix binaries I'm using have been compiled on and think that this may be the problem, but, of course, I may be wrong. And I wonder if somebody else has experienced anything like that.

new topic     » goto parent     » topic index » view message » categorize

17. Re: Can OpenEuphoria Help Solve This?

Pirx said...

This is something strange. I just run simple script calculating 10000 numbers of PI and the results on my laptop are:

.. Luajit is 10 times faster than compiled Euphoria and 20 times faster than interpreted Euphoria. Also, compiled Euphoria code seems to run with two different speeds. It's very fast at the beginning then suddenly slows down. Strange...

You could be right but I'd still like to actually see those scripts to make sure we really are comparing apples with apples..

Spock

new topic     » goto parent     » topic index » view message » categorize

18. Re: Can OpenEuphoria Help Solve This?

Pirx said...

Phix, on the other hand, doesn't work on them at all - segmentation fault is all I get.

Can you install evans debugger and run edb --run ./p

I have 0.9.18 installed (right at the bottom of that page): I know I had problems compiling 0.9.20, and possibly 0.9.21, which may have been fixed with the .tgz file, but have only learnt of the existence of 1.0.0 some 30 seconds ago.

Pete

new topic     » goto parent     » topic index » view message » categorize

19. Re: Can OpenEuphoria Help Solve This?

_tom said...

The Phix algorithm from Rosetta Code:
From Lua Rosetta Code:

n = 1000 

The test method:

system( "p p_pi.ex" ) 
? time() - t 

Phix is three time faster than LuaJIT.

Firstly, system() returns before the command is complete, you must use {} = system_exec() instead.

Secondly, that horrible golf entry calculates 2400 places, so you'd need to change the n in the lua entry to 2400.
I now have a working luajit here, and found that Phix was a full 16 times faster!

However, it is a completely different algorithm, calculating 4 digits per iteration for one thing, so here is the lua one translated to phix (and upped to 2400 dp, and sneakily optimised a bit):

integer n = 2400, 
        len = floor(10*n/3) 
sequence a = repeat(2,len) 
integer nines = 0, 
        predigit = 0 
string res = "" 
    for j=1 to n do 
        integer q = 0 
        for i=len to 1 by -1 do 
            integer x = 10*a[i]+q*i, 
                    d = 2*i-1 
            a[i] = remainder(x,d) 
            q = floor(x/d) 
        end for 
        a[1] = remainder(q,10) 
        q = floor(q/10) 
        if q==9 then 
            nines = nines+1 
        else 
            integer nine = '9' 
            if q==10 then 
                predigit += 1 
                q = 0 
                nine = '0' 
            end if 
            res &= predigit+'0'&repeat(nine,nines) 
            predigit = q 
            nines = 0 
        end if 
    end for 
    res &= predigit+'0' 
    puts(1,res) 

Now, slightly fairer, I'm seeing Phix being 2.35 times faster than Lua - to be honest that quite surprises me.

Pete

PS: lua (and LOVE) are really quite good, and definitely have some advantages, but they simply don't quite get me further enough along. If only LOVE had IUP working on android, or lua.js was not 50MB...

new topic     » goto parent     » topic index » view message » categorize

20. Re: Can OpenEuphoria Help Solve This?

petelomax said...

PS: lua (and LOVE) are really quite good, and definitely have some advantages, but they simply don't quite get me further enough along. If only LOVE had IUP working on android, or lua.js was not 50MB...

Have you guys ever used Ada? I've just come across it recently, and it looks pretty good.

new topic     » goto parent     » topic index » view message » categorize

21. Re: Can OpenEuphoria Help Solve This?

euphoric said...

Have you guys ever used Ada? I've just come across it recently, and it looks pretty good.

go easy on yourself and try

https://www.modula2.org/adwm2/

new topic     » goto parent     » topic index » view message » categorize

22. Re: Can OpenEuphoria Help Solve This?

begin said...
euphoric said...

Have you guys ever used Ada? I've just come across it recently, and it looks pretty good.

go easy on yourself and try

https://www.modula2.org/adwm2/

It says Windows only. I'm not going to give any time to a language that is only for one platform. blink

But, in the interest of knowledge, what do you like about Modula-2?

new topic     » goto parent     » topic index » view message » categorize

23. Re: Can OpenEuphoria Help Solve This?

an old very reliable, bug free compiler with tons of libray code, for ex. crypto, huge numbers etc. used for a big server application 60kloc + with huge success. the program is maintained and running after 6 years. AWD has a huge program now, that is sold commercially and there are some others for large medical software. it got a nice ide and debugger, versioning etc. build in. the language has objects, can ut8 and ascii. it produced very well optimized, small programs with all check that do or not want.

new topic     » goto parent     » topic index » view message » categorize

Search



Quick Links

User menu

Not signed in.

Misc Menu