Posts by Rashakil Fol

It can't.

It's proven that in any Turing-complete language you can create a program that writes its own code as output.

Exactly. Err....well, its an italicized .

[img]http://upload.wikimedia.org/math/0/e/c/0ec6fcb6da4903ce355359d219ef3f5c.png[/img]

Therefore, i equals the square root of -1.

:)

That's not true, actually.

If you substitute -3 for x, you get [tex]\sqrt{3} = i\sqrt{-3}[/tex], that is, [tex]\sqrt{3} = -\sqrt{3}[/tex].

Also, more portable, since you're not making assumptions about character set.

My favorite number is the smallest uninteresting positive integer.

What happens when you compute fact(13)? The number is too large to be represented by a long (which has range up to 2^31-1, approximately 4 billion). That messes up the computations at that point.

That, of course, depends on what university you go to. Some schools offer bioinformatics majors. I don't think any have CS students deal with quantum computing as any big thing -- that field is just undeveloped so far.

No, you can do it without a pointer (or by using a pointer that would be there already, like the stack pointer). When you call a function with the C calling convention, you push the last argument, the second-to-last argument, the third-to-last argument, ..., and finally the first argument onto the stack, and then you call the function (which places another pointer on the stack). So when you call f in the snippet x = 2; f(x,3,4); , the stack looks something like this:

+0x000C: 04 00 00 00
+0x0008: 03 00 00 00
+0x0004: 02 00 00 00
+0x0000: <return pointer>
-0x0004: <uninitialized/junk data>

where these addresses are relative to the register %esp (or maybe %esp+4, I don't remember.) I'm assuming regular old 32-bit here...

Pass-by-reference can be implemented by letting the callee function modify the variables at +0x0004, 0x0008, and 0x000C, and then having its caller use that as its location for that variable. For example, the callee above would use +0x0004 to store the variable x. This means the address is passed to the caller implicitly, not explicitly.

The thing is, this only works if what you're passing by reference is a local variable. Otherwise, the caller would have to copy the passed-by-reference variable's value to the stack when it makes the call and then copy the new version back when the function returns. So you might say, okay, this could be efficient for passing integers by reference, but not, say, vectors or trees …

It depends what they are teaching in the discrete math class, because there's a few parts to the subject.

You've got graph theory: that's good to have knowledge for, for some algorithms, or in designing data structures. You've got basic modular arithmetic: I find myself using my experience with modular arithmetic often in college CS classes. Seriously, be familiar with modular arithmetic. You've got big O notation: that's good for describing the efficiency of algorithms and understanding what really matters when it comes to making fast software. (You'll see idiots talk about taking less instructions or coding something down in assembly when they're using retarded algorithms. You'll also see smart people doing this when their algorithm is efficient.)

A lot of times, when people complain about the uselessness of the class, there are actually places where the knowledge is useful. People say, "oh, that class is useless," but of course they think it's useless -- they went in with the attitude that it was useless, didn't learn anything, and were unable to recognize places where they could use the knowledge in the future.

Oh, and logic, and proving things. Do you have to prove anything in your discrete math class? That's the most important thing. You should be able to prove things. You should be able to prove that the code you're writing works. At least in your head, to yourself, as you write it. If you're writing code that you can't prove works, then you're just …

This is not a place where people do work for you.

You need to explain why you are unable to do this yourself, and then people might be able to give you information that would make you able to do this yourself.

Well, what are the bounds? If the numbers have length n, then the number of addition operations you have to make is between n and 2n-1, right?

So, to find theta notation for this growth, we try to find some function, f(n), where a*f(n) < number-of-addition-operations < b*f(n), where a and b are positive numbers.

That function would be f(n) = n, with a = 0.5, and b = 2. (Or you could let a = 0.9, b = 999, if you wanted.) Anyway, looking at large enough values of n, we know that the number of addition operations is greater than 0.5*n, and less than 2*n. This means that Theta(n) would describe the number of addition operations, where n is the length of the two numbers.

For multiplication, you undergo a similar procedure.

There are so many better ways you could spend your effort 'helping' children than turning down the job. If you want to do the most amount of good in the world, the right way is to find the most efficient use of money you can (maybe the most efficient charity you can find?), and put all your charitable effort into that one goal. You'd do far more good working for the company and sending that money to the most efficient charity. If you avoided the job there, it would be a selfish act, because you'd be doing the action that makes you _feel_ good, not the action that does best for the world.

I think they end up reporting these stories just because they love using the phrase 'bus plunge'.

int y = (x * 43691) >> 17;

works for all unsigned ints x (32-bit) that are less than 98303.

And you can implement the multiplication using bitwise operators too... (note that 43691 == 0xaaab, or 1010101010101011 in binary, and the reason this works is that (1 << 17) / 3 == 0xaaaa).

unsigned int divthree(unsigned int x) {
  unsigned int y;
  y = x << 1;
  y += y << 2;
  y += y << 4;
  y += y << 8;
  y += x;
  return (y >> 17);
}

If you can use 64-bit integers, you could write the following, which works on all unsigned 32-bit ints.

unsigned int divthree(unsigned int x) {
  unsigned long long y;
  y = x << 1;
  y += y << 2;
  y += y << 4;
  y += y << 8;
  y += y << 16;
  y += x;
  return (y >> 33);
}

srinivasdama: Note that

1/4 + 1/16 + 1/64 + 1/256 + ...

is equal to 1/3.

You can multiply an integer by 1/4, 1/16, and other powers of 2 with the >> operator.

Well, I know that. Why can't you solve this problem? Where in the solution process do you go, I don't know how to do this? You can't just draw a blank. That's not how problems get solved. Do you understand what the problem's asking you to do? Yes? No?

If yes, then do you know what big theta notation means? Yes? No?

If yes, then do you know how to calculate the minimum and maximum possible number of addition operations when adding two numbers? Yes? No?

If yes, then can you express those bounds using theta notation? Yes? No? (Here, "No" might mean that it's just impossible.)

Which part can't you do? That's the part you need to identify.

You're using XML to preprocess TeX files! TeX! There's already a way to preprocess TeX files; the TeX language itself! It has features for that! Why would you use this? Seriously.

Also, you have several problems: First, you're using XML. That makes things harder. Second, what's with the 'print' element? There's no need to wrap that text in any 'print' element.

Why are you using backslash codes like \n in XML text? Have you seen any other XML format do that?

It's easier to whip up a Perl script than to write out an XML file.

If anything, instead of XML, I'd do something along these lines:

%%
#hello $param1 $param2
@text
#endofhello
%%
Hello Mr. $param1,

@text

Sincerely, $param2
%%
#foobar $k
@text :: $x $y
#/foobar
%%
Listing of $k:

Item: $x\t Zing: $y
%%

Then

#hello Quux Khanbar

How are you doing?  Here are our Dingbats:

#foobar dingbats
Cat 7
Dog 9
Zephyr 23
toozaloo 19
Zamboni -3
#/foobar

#endofhello

gets processed into, well, you can figure it out.

That's funny. Your version prints

1
2
3
4
5
6
7
8
9
10
-bash: pause: command not found

You 'read many books about c++'? Have you actually written anything in the language?

You could try making a program that scans people's written words and makes fun of them for not being able to put sentences together.

Yes.

First, do you understand theta notation? Do you understand it well enough to tell me, using theta notation, how long this algorithm takes to run?

for i = 1 to n
  for j = 1 to i
    sum = sum + 1

I'll assume yes.

So, when adding two seven-digit numbers together, e.g.

abcdefg
+ hijklmn

How many times do you add two one-digit numbers? (It depends on how many times you have to carry, but there's an upper limit and a lower limit.)

So, my question for you is, and this is possibly a hard question, but one you need to be good at answering in order to be good at thinking about hard problems: What, precisely, do you not understand?

http://eternallyconfuzzled.com/tuts/hashing.html

Output the characters in a loop. Keep track of the previous character you've output. If it was a space, then if the current character is a space, don't output it.

Another Perl version:

s/./'print "'.(-64+ord $&)."\n\""/gee for $x = "ABCDEFGHIJ"

"print [1..10]" you say? Funny you should mention that!

A Haskell version:

main = print [1..10]

Hello everyone. I recently came accross the concept of Turing completeness (in languages). I was wondering, is there a general method for determining if a language is Turing complete? Or is it one of those intuitive things where you just have to look at it for a while and go "oh yes" (or "oh no)? When I say a general method I mean a mathematical proof. This isn't a support question, I'm just curious. Any answers appriciated.

Steven.

Yes. Show that any program written in language X can be written in language Y, where X is a known Turing-complete language. A convenient way to do this is to write an interpreter for X. A convenient choice for X is Brainfuck. If you can write a Brainfuck interpreter in a language, then that language is Turing complete.

Of course, no language run on computers is _truly_ Turing-complete, because computers have limited memory (this makes them, theoretically-speaking, equivalent to deterministic finite automata).

See http://www.cs.rpi.edu/~buschc/courses/modcomp/fall2006/schedule.html for more details. These are slides from a class I'm taking. I think the slides are quite good (since I've only spent a total of 3 hours in class), and somewhere along the line, it has a few examples of proving that certain types of computing machines are Turing-complete. (And it gives a definition of a Turing machine.)

Who cares? Both ways are perfectly fine. If you want your cars to be smart enough to understand direction strings, that works as well as having them be dumb. You've got to put the intelligence somewhere.

Yes.

Oh, so you just mean a table with two columns: input strings and acceptance/rejection?

Well, anyway, you should probably think about information storage. When you're partway through the string, what piece of information will you need to have retained about the previously read parts of the string? How are you going to represent that information? You have two places to represent that information: your current node within the graph of the automaton, and your stack. What piece of information do you need to retain and update each step of the way?

Why would you need help? Specifically, what don't you know how to do? More specifically, if somebody asked you to run a program manually, on paper, would you not know how to do it? You should know how to do that... If so, then you should be able to write a program that follows the same steps you would follow when you manually run a program.

It has to do with the C++ standard. The standard says, "use int", so that's what you should use. The reason you should use int is, void main is not necessarily accepted by every compiler.

What do you mean by 'a table'?

Look at the source code for some free, open source editors out there and see what they do.

I'd imagine I'd make a mini-language for describing source code colorization and then use that to colorize source code.

C and C++ should be abandoned (or substancially modified) as the default languages used for the writing of native executables and operating systems.

The Linspire team has already abandoned C and C++ and use Haskell as their preferred language for core OS development. That doesn't mean the kernel shouldn't be in C, though -- it's small enough (assuming it is) and important enough that it can be paid close attention to.

The reason? Giving the programmer arbitrary control over pointers is un-necessary and leads to many bugs. What should be written in C/C++ is native compilers (or interpreters) for other languages that don't allow arbitrary pointer control (i.e. Python, Perl etc.). Don't get me wrong, C/C++ has many good points. But I think that in most cases pointer control should be left to the compiler to deal with, leaving the programmer free to deal with what the program actually does (i.e. manipulate variables).

Programs don't manipulate variables; they interact with the kernel and with hardware. Some programming languages don't let you modify variables.

And C and C++ are terrible languages for writing native compilers (or for anything).

I think future operating systems should use a no kernel approach where all processes run in the same memory space. This has already been done to an early development stage with Unununium (http://unununium.org). If arbitrary pointer control is not possible in the default language, protected mode addressing is not necessary and will come to be seen as inefficient …

Some of these comments remind me of the Blub Paradox

What? Why are you having problems? I think it would be helpful if you told us what course you're taking, and what expectations they have of you. Is this an intro compsci class? It sounds like it's not. You said in the other thread that you're a masters student in HCC. Human-Centered Computing?

So, tell us a few things:
1. What course you're taking, and what prior knowledge/experience this course expected of its students.
2. How many days you have to figure things out.

Or how about 1.00...

But WaltP's colors are all wrong. Yours are better. (Mine are the best. No you can't have them :P)

I know! Let's through obscure languages at the feature!

factorial 0 = 1
factorial n = n * factorial (n - 1)

It doesn't look like you have Haskell highlighting yet.

((call/cc call/cc)
 (lambda (f)
   (display "Hello, world!")
   (newline)
   (f f)))

Well at least you have Scheme. But the highlighting is broken, since it treats display and newline like keywords, when they're just built-in procedures.

Well, technically, that prints 12345678910.

Here's a Perl 6 version:

say for 1..10

Here's another Haskell one:

main = mapM_ print [1..10]

x - x^(1/3) - 2 is not a polynomial.

Adding Em would ward off divide by zero errors. It's much more likely for a function to have two floating point numbers where it evaluates to the same value than to have a function that has two points where the difference is Em. The only place where the difference of floating point representations could evaluate to Em (or negative Em), for continuous functions, is about the origin, if the function intersects the origin, unless the function has a zero where the first non-zero derivative is absuuuuurdly infinitesimal. (In those situations usually you'd be using different units to scale your function up, anyway.) You could also get the value +/- Em for laaaarge values of x, if lim (x->infinity) f(x) = 0.

For example, if you're using doubles to represent your numbers, and you have two numbers 2 <= x1 <= x2 <= 3, then evaluating (x2-x1) will produce one of the discrete values 0, 2^-52, 2*2^-52, 3*2^-52, 4*2^-52, 5*2^-52, ... (Maybe the exponent is -53 or -51; I don't care to check.) If it's 0, then adding Em makes the denominator nonzero, and if it's nonzero, then adding Em doesn't change the denominator.

Thus adding Em in your case (where your root is not zero, and where you don't have two values xi, x{i+1} such that f(xi) = f(x{i+1})) has exactly no impact on convergence, and no impact on any of your xn values.

operator() lets your values look like functions.

For example

struct greeter {
  std::string greeting_text;

  int operator()(const std::string& greetee) {
    std::cout << greeting_text << ", " << greetee << "!" << std::endl;
    return 12345;
  }
};

// later:
greeter alien_greet, programmer_greet;
alien_greet.greeting_text = "Greetings";
programmer_greet.greeting_text = "Hello";
int x;
x = alien_greet("earthling"); // prints "Greetings, earthling!"
programmer_greet("world"); // prints "Hello, world!"

std::cout << x << std::endl; // outputs 12345

Generally speaking, operator() tries to provide the ability to create functions that contain internal parameters of their own.

The best way to verify the correctness of your answers is to try a few example values for your parameters and see what happens. See if you can notice a pattern. For example, if I were given the code for (i = 0; i < 2 * n; ++i) { x = x + 1; } and wanted to know how many times (x = x + 1) was evaluated in terms of theta notation of n, I might try a few example values for n and see what happens. For example, if n were 1, it'd get executed twice, and if n were 2, it'd get executed 4 times, and in general 2*n times, so the number of times it gets executed is Theta(n) times. (Saying Theta(2*n) or Theta(n + 1) or Theta(n/100) would also be equivalent to Theta(n), since they're all within a constant multiple of each other for large enough values of n.)

For the first problem, pick some values for n (and start x at zero, say). Then see the pattern. Yes, your answer is extremely wrong :-) And it's best to work out the code by hand than put it in a computer.

If you need to prove your answers, considerably more effort is required.

All you did is put parentheses after some things?

You won't get a good answer if you can't even figure out what you want. First, you asked how to differentiate an equation (which raises the question, how do you want to represent an equation?). Then you asked how to solve a differentiable equation (which raises the question, how do you want to represent an equation?). Which do you want?

You could try learning how to read. He has (or had) three days to pick a title, not to do the entire project.

You can use % 10 to find the units digit of a number. For example, n % 10 gives the units digit of n. You can then use / 10 to divide an integer by ten. For example, n / 10 divides n by ten.

So, 1697 % 10 simplifies to 7, and 1697 / 10 simplifies to 169. You can do this in a loop to fill a list or vector or array with the digits of your number, and then use a lookup table (an array with strings "zero", "one", ..., "nine") to get a string form of the number.

Haven't you read the homework policy? Do your own homework.

What are you talking about? The time complexity is a mathematical expression describing the growth rate of an algorithm's running time as an input parameter varies. Running an algorithm 1000 times wouldn't give you any clue about the time complexity.

yenh, I don't feel like writing out a tutorial every time this question occurs, so here's a link to some explanation from a previous thread. http://www.daniweb.com/techtalkforums/thread13488-2.html

I don't see why a math person would have any problem with that reasoning.

Um, why don't you write it yourself?

See http://en.wikipedia.org/wiki/IEEE_754 for information on how float and double are typically implemented.

Reverse postorder means you traverse each node's children from right to left.

Life's too short to worry about operating systems.