Author |
Message |
|
Iambian
Advanced Member
Joined: 13 Mar 2004 Posts: 423
|
Posted: 28 Sep 2009 05:44:59 pm Post subject: |
|
|
The binary number is stored in a list with a length only as long as it is needed to increment the number. The code that I have that does this is the following, considering that Z is the number of digits...
Code: 1→W
For(W,Z,1,-1)
L1(V)→U
U xor W→L1(V)
U and W→W
End
I want to know how I'd make this work any faster, or if there's any faster method. The current method stores the number from right to left but if it's any faster to do it in any other way, as long as the digits are still their own elements in the list, I'd like to know how.
This is being used to generate truth tables given an input function.
EDIT: For those reading this thread the first time around, a correction (not in this post) was made to the code above that replaced the "W" in the For(...) command with "V".
Last edited by Guest on 28 Sep 2009 08:18:51 pm; edited 1 time in total |
|
Back to top |
|
|
Weregoose Authentic INTJ
Super Elite (Last Title)
Joined: 25 Nov 2004 Posts: 3976
|
Posted: 28 Sep 2009 06:48:54 pm Post subject: |
|
|
Is that the right code? I can't make sense out of it.
Last edited by Guest on 28 Sep 2009 06:49:18 pm; edited 1 time in total |
|
Back to top |
|
|
Iambian
Advanced Member
Joined: 13 Mar 2004 Posts: 423
|
Posted: 28 Sep 2009 06:55:44 pm Post subject: |
|
|
That code is currently being used in the program with success.
The code is extracting a digit from the list then performing binary addition to it. The carry is preset to "1" start the increment. If the two numbers are different (1 and 0) then 1 gets stored back. If both was a zero, a zero results. If both were a "1", it would correctly store back a zero since 1+1 = 10. The "and" after the "xor" is used to determine if both were a one, and if so, store that carry to W. Otherwise, it'll always be reset.
I don't know if I explained this one correctly, but the digital logic stuff last Monday POISONED my mind. That's what I came up with. |
|
Back to top |
|
|
Weregoose Authentic INTJ
Super Elite (Last Title)
Joined: 25 Nov 2004 Posts: 3976
|
Posted: 28 Sep 2009 07:08:10 pm Post subject: |
|
|
But, all this does is toggle the Vth bit. |
|
Back to top |
|
|
Iambian
Advanced Member
Joined: 13 Mar 2004 Posts: 423
|
Posted: 28 Sep 2009 07:14:40 pm Post subject: |
|
|
It's an adder. It toggles the bit only if it can be toggled. The carry determines whether or not that particular bit is to be toggled and it maintains what toggling it means to the next bit it has to work on.
EDIT: Wait. I found what you were talking about A min.
EDIT2: The conditions in For( is messed up. V looked a lot like W when I did it >.<
Code: 1→W
For(V,Z,1,-1)
L1(V)→U
U xor W→L1(V)
U and W→W
End
Looks like it's correct now. Just one letter off and BAM!
Last edited by Guest on 28 Sep 2009 07:18:14 pm; edited 1 time in total |
|
Back to top |
|
|
Weregoose Authentic INTJ
Super Elite (Last Title)
Joined: 25 Nov 2004 Posts: 3976
|
Posted: 28 Sep 2009 07:27:20 pm Post subject: |
|
|
Beautiful, now we're talking. This was also one of the first questions that I posted when I joined UTI! :)
To directly convert N to its binary form: int(2fPart(N.5^seq(Z,Z,B,1,-1. So, put that in a For( loop, maybe. What you already have there is indeed how adders work, so it's probably already optimal in terms of function. At any rate, I'll do some binary tables for fun and perhaps post something later.
Last edited by Guest on 05 Jul 2010 08:00:32 am; edited 1 time in total |
|
Back to top |
|
|
calc84maniac
Elite
Joined: 22 Jan 2007 Posts: 770
|
Posted: 28 Sep 2009 07:36:02 pm Post subject: |
|
|
Code: Z→V
While L1(V
0→L1(V
V-1→V
End
1→L1(V
It will crash if there's an overflow though. :(
Edit:
Oops, forgot a line
Last edited by Guest on 28 Sep 2009 07:37:31 pm; edited 1 time in total |
|
Back to top |
|
|
ztrumpet
Active Member
Joined: 06 May 2009 Posts: 555
|
Posted: 28 Sep 2009 07:40:58 pm Post subject: |
|
|
Weregoose wrote: int(2fPart(N.5^seq(Z,Z,B,1,-1 The seq can be faster as (B+1-cumsum(binomcdf(B-1,0
Last edited by Guest on 05 Jul 2010 08:00:49 am; edited 1 time in total |
|
Back to top |
|
|
Weregoose Authentic INTJ
Super Elite (Last Title)
Joined: 25 Nov 2004 Posts: 3976
|
Posted: 28 Sep 2009 07:53:42 pm Post subject: |
|
|
Consider this a beta:
Ans+(sum(not(Ans))≤cumSum(not(Ans
(Ans<2)Ans
[EDIT] – Saved a couple bytes.
Easy modification to count backwards – take out the not('s.
In both cases, remove sum( and swap out ≤ for ≥ to reverse the bit order.
[EDIT×2]
Ans xor Ans=cumSum(Ans. That's as simple as it gets.
Last edited by Guest on 05 Jul 2010 08:01:12 am; edited 1 time in total |
|
Back to top |
|
|
DarkerLine ceci n'est pas une |
Super Elite (Last Title)
Joined: 04 Nov 2003 Posts: 8328
|
Posted: 28 Sep 2009 10:16:43 pm Post subject: |
|
|
You mean Ans xor not(Ans)=cumSum(not(Ans? Because that last bit doesn't seem to work.
Last edited by Guest on 05 Jul 2010 08:01:36 am; edited 1 time in total |
|
Back to top |
|
|
Weregoose Authentic INTJ
Super Elite (Last Title)
Joined: 25 Nov 2004 Posts: 3976
|
Posted: 28 Sep 2009 10:29:42 pm Post subject: |
|
|
DarkerLine wrote: You mean Ans xor not(Ans)=cumSum(not(Ans? Because that last bit doesn't seem to work. Either will produce all binary numbers of a given length. The first one just happens to do so in reverse (by count as well as order of digits), so it's only incorrect in that it's not a binary increment as requested by the title.
Last edited by Guest on 05 Jul 2010 08:02:20 am; edited 1 time in total |
|
Back to top |
|
|
Iambian
Advanced Member
Joined: 13 Mar 2004 Posts: 423
|
Posted: 28 Sep 2009 10:53:47 pm Post subject: |
|
|
Actually, any one of these could be made to work.
Thank you for all the work you've done! Already, the program is running far faster for it, and it stands to get a little faster as I rework it to accept the following:
Ans xor Ans=cumSum(Ans
With the digits reversed but not inverted, that's actually how I wrote my truth tables down on paper.
Last edited by Guest on 05 Jul 2010 08:00:18 am; edited 1 time in total |
|
Back to top |
|
|
Iambian
Advanced Member
Joined: 13 Mar 2004 Posts: 423
|
Posted: 29 Sep 2009 10:47:53 pm Post subject: |
|
|
EDIT: Sorry for the double post.
While still somewhat related to the topic, I'm also looking for ways to convert that binary number to its gray code equivalent. So far, this is what I have for the process, but it only works for binary numbers written with the least significant digit on the right side.
Code: abs(ΔList(augment({0},Ans
I'm almost convinced that the process I need these gray codes for would be better done with a hardcoded lookup table, but then that would rob me of trying to learn the process. Especially if I need to do it with sufficiently large numbers.
Last edited by Guest on 29 Sep 2009 10:48:18 pm; edited 1 time in total |
|
Back to top |
|
|
thornahawk μολών λαβέ
Active Member
Joined: 27 Mar 2005 Posts: 569
|
Posted: 01 Oct 2009 07:11:19 am Post subject: |
|
|
Iambian, I assume you've peered at Arndt's Matters Computational? He's got stuff in there on Gray codes...
thornahawk |
|
Back to top |
|
|
|