Wikipedia:Reference desk/Archives/Computing/2019 June 17: Difference between revisions

Revision as of 00:26, 29 June 2019

Latest revision as of 15:45, 9 May 2022

(2 intermediate revisions by one other user not shown)

Line 33:

: Here's a thing I wrote in 2008, doing a branchless strlen in C. It does indeed evaluate all possible "branches", and then uses arithmetic to report only the "successful" one. It's been 11 years since I thought about this, so I'm rusty on the minutea of the discriminator, but here goes:

{{collapse top|here be dragons}}

<sourcesyntaxhighlight lang="c">

#include <stdio.h>

Line 85:

return 0;

}

</syntaxhighlight>

</source>

{{collapse bottom}}

: The meat of the thing is the CONDFUNC. I produced three variants, none of which are exactly fun to read:

<sourcesyntaxhighlight lang="c">

#define CONDFUNC1(CONDITION,VALUE) ((VALUE)&(0xFFFFFFFFU+(!(CONDITION))))

#define CONDFUNC1(CONDITION,VALUE) ((VALUE)&((!(CONDITION))-1))

#define CONDFUNC1(CONDITION,VALUE) ((VALUE)&((~(CONDITION)&1)-1))

</syntaxhighlight>

</source>

: Does that amount to Turing completeness? I dunno. Bletchley Park's later computery things had "looping" because the "program" was actually on a physical paper loop, I don't know about the Z3.

Line 102:

: I understand what you mean fine. But it doesn't "produce output for each of those branches"; it ''calculates'' the result of each branches, and then calculates which of those to report as a final result based on a tricksy piece of bitwise arithmetic. Here's the simplest C example I can think of (which uses effectively the second CONDFUNC1 definition above) - here <code>branching_f</code> is ordinary branching code (with an <tt>if</tt> statement, that only works on a conventional computer, and <code>branchless_f</code> is the equivalent code, which produces the same result, but has no <tt>if</tt> or other branching instruction (the <tt>main()</tt> is a simple test harness to show the two are equivalent). <code>branchless_f</code> would (notionally) work on a machine like the Z3 with no branch instruction, because it only uses arithmetic and bitwise operations, and the control flow is entirely linear.

{{collapse top|another dragon}}

<sourcesyntaxhighlight lang="c">#include <stdio.h>

#define IS_EVEN(Z)((Z)%2==0)

Line 147:

return 0;

}

</syntaxhighlight>

</source>

{{collapse bottom}}

: If there were many paths, that is inefficient, and the discriminator logic at the end is concomitantly complex. But eventually there is still a single output, z. -- [[User:Finlay McWalter|Finlay McWalter]]'''··–·'''[[User talk:Finlay McWalter|Talk]] 21:03, 18 June 2019 (UTC)

Line 157:

:::: On the branchless computer, you'd have to unroll the loop:

<sourcesyntaxhighlight lang="c">

printf("%d\n", nonbranching_f(0));

printf("%d\n", nonbranching_f(1));

Line 163:

printf("%d\n", nonbranching_f(3));

// etc.

</sourcesyntaxhighlight>

:::: ... which is effectively what <tt>branchless_strlen5</tt> above does.