An NPU could give 1000x more LIPS (Re: Mercio’s Algorithm for Rational Tree Compare in Prolog)

From	Mild Shock <janburse@fastmail.fm>
Newsgroups	sci.math
Subject	An NPU could give 1000x more LIPS (Re: Mercio’s Algorithm for Rational Tree Compare in Prolog)
Date	2025-11-27 14:23 +0100
Message-ID	<10g9jbo$ofl1$3@solani.org> (permalink)
References	<106p0ct$3b6se$3@solani.org>

Show all headers | View raw

Hi,

I am spekulating an NPU could give 1000x more LIPS.
For certain combinatorial search problems. It all
boils down to implement this thingy:

In June 2020, Stockfish introduced the efficiently
updatable neural network (NNUE) approach, based
on earlier work by computer shogi programmers
https://en.wikipedia.org/wiki/Stockfish_%28chess%29

There are varying degrees what gets updated of
a neural network. But the specs of an NPU tell
me very simply the following:

- An NPU can make 40 TFLOPS, all my AI Laptops
   from 2025 can do that right now. The brands
   are Intel Ultra, AMD Ryzen and Snapdragon X,

   but I guess there might be more brands around,
   which can do that with a price tag less
   than 1000.- USD.

- SWI Prolog can make 30 MLIPS, Dogelog Player
   runs similar, some Prolog systems are faster.

Now thats is 10^12 versus 10^6. If some of the
LIPS can be delegated to a NPU, and if we assume
for example less locality or more primitive

operations that require a layering. Would could assume
that from the NPU 10^12 a factor of 1000 goes
away. So we might still see 10'9 LIPS emerge.

Now make the calculation:

- Without NPU: MLIPS
- With NPU: GLIPS
- Ratio: 1000x times faster

Have fun!

Bye

Mild Shock schrieb:
> Mercio’s Algorithm (2012) for Rational
> Tree Compare is specified here mathematically.
> It is based on computing truncations A' = (A_0,
> A_1, etc..) of a rational tree A:
> 
> A < B ⟺ A′ <_lex B′
> 
> https://math.stackexchange.com/a/210730
> 
> Here is an implementation in Prolog.
> First the truncation:
> 
> trunc(_, T, T) :- var(T), !.
> trunc(0, T, F) :- !, functor(T, F, _).
> trunc(N, T, S) :-
>     M is N-1,
>     T =.. [F|L],
>     maplist(trunc(M), L, R),
>     S =.. [F|R].
> 
> And then the iterative deepening:
> 
> mercio(N, X, Y, C) :-
>     trunc(N, X, A),
>     trunc(N, Y, B),
>     compare(D, A, B),
>     D \== (=), !, C = D.
> mercio(N, X, Y, C) :-
>     M is N + 1,
>     mercio(M, X, Y, C).
> 
> The main entry first uses (==)/2 for a
> terminating equality check and if the
> rational trees are not equal, falls back
> to the iterative deepening:
> 
> mercio(C, X, Y) :- X == Y, !, C = (=).
> mercio(C, X, Y) :- mercio(0, X, Y, C).
> 
> I couldn’t find yet a triple that violates
> transitivity. But I am also not much happy
> with the code. Looks a little bit expensive
> to create a truncation copy iteratively.
> 
> Provided there is really no counter example,
> maybe we can do mit more smart and faster? It
> might also stand the test of conservativity?

Thread

Mercio’s Algorithm for Rational Tree Compare in Prolog Mild Shock <janburse@fastmail.fm> - 2025-08-04 02:54 +0200
  The Original Ganster (OG) of Gameification: IEEE 1044.1-1995 (Re: Mercio’s Algorithm for Rational Tree Compare in Prolog) Mild Shock <janburse@fastmail.fm> - 2025-08-04 13:50 +0200
    The Bitrot called Math Stack Exchange (Re: The Original Ganster (OG) of Gameification: IEEE 1044.1-1995) Mild Shock <janburse@fastmail.fm> - 2025-08-04 13:57 +0200
      I guess its back to Hopcroft and Karp (Re: The Bitrot called Math Stack Exchange) Mild Shock <janburse@fastmail.fm> - 2025-08-04 14:12 +0200
  Szpilrajn Theorem and Suzumura Consistency (Re: Mercio’s Algorithm for Rational Tree Compare in Prolog Mild Shock <janburse@fastmail.fm> - 2025-08-06 01:53 +0200
    The good thing is we have at least Mercio’s Algorithm (Re: Szpilrajn Theorem and Suzumura Consistency) Mild Shock <janburse@fastmail.fm> - 2025-08-06 08:09 +0200
      Hopcroft and Karp’s is just Contraction (Re: The good thing is we have at least Mercio’s Algorithm) Mild Shock <janburse@fastmail.fm> - 2025-08-06 08:16 +0200
        Re: Hopcroft and Karp’s is just Contraction (Re: The good thing is we have at least Mercio’s Algorithm) Mild Shock <janburse@fastmail.fm> - 2025-08-06 08:23 +0200
  Mercios decidability was already attested in 2012 (Re: Mercio’s Algorithm for Rational Tree Compare in Prolog) Mild Shock <janburse@fastmail.fm> - 2025-08-14 20:40 +0200
    Performance of Mercio’s Total Order (Re: Mercios decidability was already attested in 2012) Mild Shock <janburse@fastmail.fm> - 2025-08-15 23:51 +0200
      Fuzzy Testing is your Swiss Knife (Was: Performance of Mercio’s Total Order) Mild Shock <janburse@fastmail.fm> - 2025-08-15 23:54 +0200
        Yeah, we have another name! (Re: Fuzzy Testing is your Swiss Knife) Mild Shock <janburse@fastmail.fm> - 2025-08-16 12:40 +0200
          Monte Carlo sampling the frontier version (Re: Yeah, we have another name!) Mild Shock <janburse@fastmail.fm> - 2025-08-16 12:44 +0200
  An NPU could give 1000x more LIPS (Re: Mercio’s Algorithm for Rational Tree Compare in Prolog) Mild Shock <janburse@fastmail.fm> - 2025-11-27 14:23 +0100
    Zeus: A Language for Expressing Algorithms in Hardware (Re: Neural Network based dif/2 respectively (#\=)/2) Mild Shock <janburse@fastmail.fm> - 2025-11-27 15:02 +0100
    100% serious Giga Logical Inferences per Second (GLIPS) (Re: An NPU could give 1000x more LIPS (Re: Mercio’s Algorithm for Rational Tree Compare in Prolog) Mild Shock <janburse@fastmail.fm> - 2025-11-28 14:53 +0100

csiph-web