Questions tagged [fixed-point]
The fixed-point tag has no usage guidance.
24
questions
1
vote
0answers
28 views
What are the fixed-points of the Y combinator?
Since the Y combinator itself is a function (albeit a higher-order one), I was wondering what the fixed-points of Y itself are.
0
votes
0answers
21 views
Computer arithmetic algorithm: what might I be doing wrong?
So I'm working with the following differences equation:
$$y_n=\alpha y_{n-1}+(1-\alpha)x_n$$
I know this works with 16-fixed point arithmetic, and given some samples I'm trying to figure out how the ...
0
votes
0answers
31 views
Is there a Q-like number format for decimal fixed-points?
As per Wikipedia, the Q number format is
A binary fixed point number format where the number of fractional bits (and optionally the number of integer bits) is specified. For example, a Q1.14 number ...
0
votes
0answers
13 views
Multiplication of two binary numbers in fixed point arithmetic
So I'm performing some operations with fractional numbers in a 16-bit FIXED-POINT processor.
I have to multiply the numbers $\ x=-6.35$, represented in $\ Q_{11}$, and $\ y=-0.1$, represented in $\ ...
0
votes
0answers
26 views
Confused about adding numbers in fixed-point
So I'm performing some operations with fractional numbers in a 16-bit FIXED-POINT processor.
I have to add the numbers $\ x=-7.1$, represented in $\ Q_{12}$, and $\ y=0.75$, represent in $\ Q_{15}$. ...
1
vote
0answers
43 views
Is there a term for the inverse of a fixed-point operator?
When working with recursion it is often useful to find the least or greatest fixed points of a morphism, often using a fixed-point combinator. When working with recursion schemes, the inverse ...
1
vote
1answer
24 views
How do we know that $F^{n + 1}(\overrightarrow{\emptyset}) = F(F^n(\overrightarrow{\emptyset}))$?
I am currently studying the textbook Principles of Program Analysis by Flemming Nielson, Hanne R. Nielson, and Chris Hankin. Chapter 1.3 Data Flow Analysis says the following:
The least solution. The ...
3
votes
1answer
128 views
How to prove that the Church encoding, forall r. (F r -> r) -> r, gives an initial algebra of the functor F?
The well-known Church encoding of natural numbers can be generalized to use an arbitrary (covariant) functor F. The result is the type, call it ...
1
vote
0answers
70 views
Find the fixed point of a recursive functional?
A functional is a function which takes another function as a parameter.
The fixed point of a function is an input such that
F(x) = x
Given an example functional,
<...
0
votes
1answer
53 views
Termination of Z combinator with call-by-value
I am trying to build my own λ-calculus interpreter. So far it supports both call-by-value and normal order.
I now want to try recursion via fixed points. The $Y$ combinator works with normal order, ...
1
vote
1answer
88 views
Fixed Points of Factorial Function
(This is taken from the book Semantics with Applications)
I'm trying to determine the fixed points for the following block:
...
0
votes
0answers
34 views
Trying to determine Fixed Points
I'm basically trying to solve 4.2
(Taken from Semantics with Applications)
As I see it, the functional F will be defined like so:
...
5
votes
1answer
508 views
Fixed point of hash
Are hashing algorithms constructed to guarantee that no fixed point exists?
My assumption is not, because I don’t see what utility that would have. (Please correct me if I’m wrong.) As such, purely ...
5
votes
1answer
309 views
Logical characterization of P versus NP problem (and references for least fixed point logic)
Wikipedia says the following (and more) about the logical characterization of the P versus NP problem here:
Thus, the question "is P a proper subset of NP" can be reformulated as "is existential ...
5
votes
2answers
741 views
Why Does the Fixed Point Theorem Apply to Quines?
A quine is a program that outputs its own source code without taking in any input. An example would be this (taken from here)
...
1
vote
1answer
2k views
How does conversion from fixed-point to floating-point happen?
I came across to the code that convert 32-bit signed fixed-point number (16.16) to a float and it looks like (pseudocode)
floating = fixed / 65536.0
Could you ...
1
vote
0answers
33 views
Hebbian rule doesn't get to a fixpoint
I'm trying to implement an Hopfield Network for pictures of 32x32 bits either 1 or -1;
I have these 3 pictures and I transform each of them in a vector of 1024 elements.
Then I take the 3 vectors and ...
1
vote
1answer
148 views
Is Datalog negation and the built-in predicate $ \neq $ similar?
I was reading "Principles of Database & Knowledge-Base Systems, Vol. 1" by Jeffrey D. Ullman. There is a chapter about Datalog negation and as I was seeing the problems of negation I kept thinking ...
1
vote
1answer
472 views
Neural Networks: Simulate the working of Dynamic Fixed Point representation of the weights on hardware
I am looking to implement a neural network on hardware using Verilog. I have completed and tested with floating point representation and a 20 bit fixed point representation. I want to further reduce ...
5
votes
2answers
1k views
What is a fixpoint?
Could someone please explain me, what is a fix point?
I caught the minimum explanation about fix point from the website:
After infinitely many iterations we should get to a fix point where
...
3
votes
1answer
119 views
Why doesn't this quine-less language contradict Kleene's recursion theorem?
Kleene's recursion theorem implies that every Turing complete programming language that satisfies certain properties have quines. This website claims that this is incorrect, and that there is a Turing ...
0
votes
2answers
630 views
Decimal to Fixed Point Conversion
I am having trouble to get the intuition behind the following approach:
We take the fraction point (say: .642) and continuously multiply by 2,
taking whatever ends up right of the point as our next ...
3
votes
2answers
53 views
Notation for a Kleene fixed point with a starting element
Assume a CPO $Q,\leq$ and a Scott-continuous function $f : Q \rightarrow Q$. As it is known, the chain $\bot \leq f(\bot) \leq \ldots \leq f^n(\bot)$ (where $f^n$ denotes the function $n-1$-times ...
11
votes
2answers
3k views
Why is least fixed point (lfp) important in program analysis
I am trying to get a big picture on the importance of least fixed point (lfp) in program analysis. For instance abstract interpretation seems to use the existence of lfp. Many research papers on ...
